Why does use of vector gives TLE while map does not ?
Difference between en1 and en2, changed 68 character(s)
In this submission -> [submission:306874451] as you go through the solve function you will see that I have used ↵
↵
~~~~~↵
vector<ll> freq(2e5+1,0);↵
~~~~~↵
↵
as you can see it got Time Limit exceeded on test case 2, after replacing the vector with map in the following submission -> [submission:306878312]↵
↵
~~~~~↵
map<ll,ll> freq;↵
~~~~~↵
↵
Problem Link -> [problem:1775b]↵
↵
It got accepted, now according to my knowledge map takes O(log N) time to access its elements while vector takes O(1) time.↵
↵
So in the worst case scenario shouldn't the vector be better ?↵
↵
Problem Link -> [problem:1775b]↵
↵
↵
↵
[BTW This is my first blog so please forgive me if I made any mistake.]↵
↵
↵
↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English alphaaditya 2025-02-19 18:00:26 68
en1 English alphaaditya 2025-02-19 17:58:26 710 I appreciate any help with this issue and Thanks in advance. (published)