Блог пользователя dakshdixit183

Finding Elements Lesser than X in set/multiset and then delete that element
Автор dakshdixit183, история, 15 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
15 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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]);
→ Ответить