dakshdixit183's blog

Finding Elements Lesser than X in set/multiset and then delete that element
By dakshdixit183, history, 9 months ago, In English

I am doing a problem which requires similar operation in which we have to find element smaller than x then delete it from multiset then find for another x. I am using an approach that is giving TLE for 10^5 constraints

Problem Link

My Code

Is my method to find that element wrong or is it anything else. PS -> I am not very clear on how to find Elements Lesser than X in set/multiset and its working I used auto it = *lower_bound(st.rbegin(),st.rend(),a[i],greater()); As I saw it in blog can anyone also explain how it works

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

You are using the wrong lower_bound function. That one uses advance to move between iterators, which is linearithmic in number of steps for a multiset and set, so your time complexity is not $$$\mathcal{O}(\log n)$$$, but rather $$$\mathcal{O}(n \log n)$$$, for each query.

Define your multiset as

multiset<int, greater<int>> st;

Then use

auto it = st.lower_bound(a[i]);
→ Reply