Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### techwiz911's blog

By techwiz911, history, 5 years ago, ,

I was attempting the following question 310D

Here is my submission that timed-out TLE

And here is my submission that was accepted AC

As you may have observed, the only change I made from the TLE code to AC code was

  it=lower_bound(s.begin(),s.end(),mp(lo,o));


to

  it=s.lower_bound(mp(lo,o));


where "it" is a set iterator.

Just changing this, the time on Test #11 was reduced from >3000ms to 264ms. Can any one shed some light on why this happened? Thank you.

• -4

 » 5 years ago, # |   +10 I think without be sure that the first runs in 0(N), and the second in O(logN).
•  » » 5 years ago, # ^ |   0 Okay. But why the change in behaviour for the same function? I mean what goes behind the curtains?
 » 5 years ago, # |   +11 See complexity of these methods 1 2
•  » » 5 years ago, # ^ |   0 Thanks a lot. Glad I got to know this now, getting TLE in a contest because of this would have hurt.
 » 5 years ago, # |   0 Actually you will find everything about C++ in this site. So, you can always check anything there.http://www.cplusplus.com/
 » 5 years ago, # |   +11 The key is, that the lower_bound in the algorithm package has no knowledge about the internal structure of set. It can do a binary search for random access containers, but not for set. For set, it has to go through all elements step by step.On the other hand, set's lower_bound can leverage its knowledge about its internal structure, and can do it log n runtime.
•  » » 5 years ago, # ^ |   +6 One minor technical detail is that the lower_bound function from algorithm actually always does a binary search.It's just that for forward iterators such as set::iterator that are not random access iterators advance(iterator,constant) is slow. More precisely, you need roughly k operations to advance an iterator by k, and this is what makes the total time complexity linear instead of logarithmic.(Hence, lower_bound on a container that only has forward iterators will usually be a bit slower than find.)
 » 5 years ago, # |   0 If only i had a nickle everytime I see lowerbound issue in set