Strange problems about C++ map in 1771F
Difference between en1 and en2, changed 346 character(s)
My submission [submission:184727292] in contest got Time Limit Exceeded on test 30.↵

When I submit this solution in C++14 [submission:184832244] , it passes in 592ms.↵

Then I change the map into vector [submission:184832165] , and it passes in 296ms.↵

So it seems that the map runs too slow, and in test 30, $N=23355$, which means there are only $7e4$ operations of map, but strangely it costs more than $1s$.↵

Map should run in exactly $O(nlogn)$ , so what could possibly be the problem?↵

**UPD**: Thanks to [user:beep_boop,2022-12-12] and [user:Perpetually_Purple,2022-12-12] , a similar problem occurred in this [blog](https://mirror.codeforces.com/blog/entry/99038).↵

The solution [submission:184859925] is to read all the elements first then add them to the map.↵

I still have no idea why map behaves so strange in this case. :(↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English sjc061031 2022-12-12 11:01:23 346 Tiny change: 'ry/99038). The soluti' -> 'ry/99038).\n\nThe soluti'
en1 English sjc061031 2022-12-12 04:50:16 537 Initial revision (published)