This is the leetcode problem from a recent contest: https://leetcode.com/problems/minimum-number-of-seconds-to-make-mountain-height-zero/
For some reason, this solution gives a TLE: https://ideone.com/00tSfJ.
I have an alternative solution which passes, my question is why does the above solution give TLE?
This solution should not be giving TLE because:
-the while loop can have upto 56 turns (since 2^56 > 1e8 * 1e8)
-the for loop upto 10^4 turns
-and, the map.upper_bound() would take 17 turns (since, log_base2(2^17) > log_base2(10^5) > log_base2(no. of items in map))
So overall, 9.52 * 10^6 operations. But I still get a TLE here. Please help me understand this better.
PS: I know that above is a simplification because complexity represents order of growth with respect to input size but I still don't see why the above solution should not pass.