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. :(↵
↵
↵
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. :(↵
↵
