How use of upper_bound deters time limit exceeded??

general
, ,
1

I’m solving NOTATRI problem. After figuring out logic and algorithm, I submitted two solutions. One is using upper_bound from algorithm header and other one is doing just same as it. But later one didn’t succeed in getting accepted, it got TLE. How does this happen ??

  1. http://www.codechef.com/viewsolution/2387957
  2. http://www.codechef.com/viewsolution/2387973
2

The STL upper_bound takes only O(log n) time where as what you do deem to be an equivalent thing runs in O(n). Maybe you can try implementing your own version of upper_bound which runs in O(log n).

2 Likes