_inaccurate's blog

How to get the position of an element in a set after lower_bound?
By _inaccurate, history, 2 years ago, In English

Hello codeforces! I'm practicing an exercise. My idea is to get the position of the selected element after a binary search on a set. Can you guys help me?..

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Ordered set

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

void solve() {
    using kth_set = __gnu_pbds::tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
    
    kth_set s;
    s.insert(3); // {3}
    s.insert(1); // {1, 3};
    auto it = s.lower_bound(0); // 1
    cout << s.order_of_key(*it) << endl; // find({1, 3}, 1) == 0
    auto it2 = s.lower_bound(2); // 3
    cout << s.order_of_key(*it2) << endl; // find({1, 3}, 3) == 1
}
→ Reply
»
2 years ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

Souce 1 — Ordered set
Source 2 — Blog

→ Reply