Yesterday , I gave contest round 702 div3 .
Problem F
Solution 1(https://codeforces.com/contest/1490/submission/107661957)
Solution 2(https://codeforces.com/contest/1490/submission/107661859)
In Solution1 I used unordered_map which gave me tle and than i used map in solution 2 it didn't.
Can anyone explain how does unordered_map gave tle and map won't?
Exactly same thing happened with me too, It was my myth that unordered_map is always faster than map . See this comment and blog u will understand. Comment Blog
In most of the cases unordered_map is faster, but not always. map is implemented using red black tree but unordered_map is implemented using list.Here is the catch what if all the values lies in a single list,then it will take O(n)instead of O(1) but map always take O(logn).For more detail you can refer documentation. :)