always_4ever_5_25__21_SS's blog

Is the build in lower_bound (when using set) slower than order_of_key and find_by_order of ordered_set?
By always_4ever_5_25__21_SS, history, 7 years ago, In English
  1. 33592102
  2. 33592281

In my first submission, I used lower_bound to find the index I want to erase. In my second one, I implement the same idea using ook (order_of_key) and fbk (find_by_order) of ordered_set. My first submission resulted in TLE (time limit 2 sec) where my second submission passed on 233 ms. I don't see any algorithmic difference. Overall Complexity for Worst case O ( n * (logn) * (logn) ). Anyone can point out what I am missing or if I am wrong?

I faced the same thing when I solved CF round 450 div2 C: Remove Extra one. Using the build in lower_bound, I got TLE but got AC when I used ook.

N.B: In my above code, lowerBound() is a user made function. lower_bound() and lowerBound() is different.

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by always_4ever_5_25__21_SS (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

lower_bound(s[ch].begin(), s[ch].end(), x) is for std::set. Use s[ch].lower_bound(x) to make the binary search in .

→ Reply