Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Fahmid_rng's blog

By Fahmid_rng, history, 12 months ago, In English

Today I solved this problem 1791F - Range Update Point Query. My first submission:345869729 & second submission:345873398 .

As you can see, those two codes are exactly the same. The only difference is: In first submission, I wrote auto it=lower_bound(all(s),l) & in 2nd submission, I wrote auto it=s.lower_bound(l), where s is a std::set . But, as far I know, both of these functions are of logarithmic time complexity. Then, why did I get TLE in my first submission? Please, explain.

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

You can go check this for why lower_bound(s.begin(), s.end(), target) takes $$$O(n)$$$ time in set.