harshad2112's blog

By harshad2112, history, 3 years ago, In English

In recent Div4 contest, I was going through PBDS, and was using less_equal PBDS, where I found out that lower Bound shows result for the upper bound and vice versa. Here's the code for the following.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

int main()
{
    tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> s;
    s.insert(4);
    s.insert(6);
    cout<<*s.upper_bound(4)<<" ";
    cout<<*s.lower_bound(4);
};

Result: 4 6

Also If I use less instead of less_equal, it shows correct output.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

int main()
{
    tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> s;
    s.insert(4);
    s.insert(6);
    cout<<*s.upper_bound(4)<<" ";
    cout<<*s.lower_bound(4);
};

Result: 6 4

Help me if I am wrong.

Full text and comments »

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