Weird time complexity issues in 1029D.

Revision en1, by I_love_Kim_Dahyun, 2020-10-12 15:51:33


I implemented the same idea as the editorial in 3 different ways.

Using stl:map : submission

Using stl:unordered_map: submission

Using stl:lower_bound: submission

I have no idea why map would give TLE and lower_bound will not, both costs O(logn). Given that lower_bound solution passes in just 312 ms, I expect map solution to pass even if runtime is a bit higher. And why on earth would unordered_map give a runtime of 1341 ms? It was supposed to be of O(1) cost. I am certain my hash_function has absolutely no chance of colliding.

Can anybody explain this behaviour...


  Rev. Lang. By When Δ Comment
en1 English I_love_Kim_Dahyun 2020-10-12 15:51:33 933 Initial revision (published)