Weird time complexity issues in 1029D.

Правка en1, от Legend_of_Azkaban, 2020-10-12 15:51:33

PROBLEM LINK

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. Язык Кто Когда Δ Комментарий
en1 Английский Legend_of_Azkaban 2020-10-12 15:51:33 933 Initial revision (published)