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.