Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

rohit7s's blog

By rohit7s, history, 5 weeks ago, In English,

I got TLE(69603836) when i used unordered_map stl, but got accepted(69603782) in map stl in C++. How?

Thanks in advance!

 
 
 
 
  • Vote: I like it
  • -12
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Operations on std::map are GUARANTEED O(logn) while on std::unordered_map are AVERAGE O(1) which means with map you get always O(logn) and with unordered_map you may get sometimes O(n) in worst case.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    unordered_map worst case usually happens when the hash function is producing collisions for every insertion in the map.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Another approach could be using binary search the answer. The problem is similar to sliding window problem. Start with binary searching length of the interval then check whether u are able to find a sliding window with atmost k distict elements or not. If yes then store the L,R of the interval.GOOD LUCK:)

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Unordered map is implemented with Hash Table, that is the reason why it's performance relies on the hash function, the average time is O(1), but worst case O(n). While map is implemented with self-balancing red-black tree, and operations are O(log n) always. That is why it is giving u TLE with map and not with unordered map, but there are times when it is the other way around, checking this blog might help u :) https://codeforces.com/blog/entry/21853