sjc061031's blog

By sjc061031, history, 10 months ago, In English

My submission 184727292 in contest got Time Limit Exceeded on test 30.

When I submit this solution in C++14 184832244 , it passes in 592ms.

Then I change the map into vector 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 beep_boop and Perpetually_Purple , a similar problem occurred in this blog.

The solution 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. :(

Full text and comments »

  • Vote: I like it
  • +145
  • Vote: I do not like it