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...
