Unexpected Result of GNU order-statistics-tree

119 Views Asked by At

I have just learned something about GNU Policy-Based Data Structures. But I got some unexpected result on this question: (the original version is described in Chinese, so I've translated it.)

You need to write a data structure which support following operations:

  1. insert number x
  2. delete number x
  3. look up number x's order("order" refers to the number of the elements smaller than this number+1)
  4. look up for the number which order is x
  5. look up for number x's prefix
  6. look up for number x's suffix
     #include <iostream>
     #include <vector>
     #include <ext/pb_ds/assoc_container.hpp>
     #include <ext/pb_ds/tree_policy.hpp>
     #include <set>

     using namespace std;
     using ost = __gnu_pbds::tree<
                            int,
                            __gnu_pbds::null_type,
                            less<int>,
                            __gnu_pbds::rb_tree_tag,
                            __gnu_pbds::tree_order_statistics_node_update>;

int a;
int main() {
    ost s;
    int n;
    cin>>n;
    int opnum;
    ost::iterator i;
    for(int j=1;j<=n;j++)
    {
        cin>>opnum;
        switch(opnum)
        {

            case 1:
                cin>>a;
                s.insert(a);
                break;
            case 2:
                cin>>a;
                s.erase(a);
                break;
            case 3:
                cin>>a;
                cout<<s.order_of_key(a)+1<<endl;
                break;
            case 4:
                cin>>a;
                cout<<*s.find_by_order(a-1)<<endl;
                break;
            case 5:
                cin>>a;
                i=s.lower_bound(a);
                --i;
                while(a<=*i)
                    --i;
                cout<<*i<<endl;
                break;
            case 6:
                cin>>a;
                cout<<*(s.upper_bound(a))<<endl;
                break;
        }
        /*
        for(auto i:s)
        {
            cout<<"\t"<<i<<endl;
        }
        */

    }
    return 0;
}

But only 55% of data points are accepted. And in Wrong Answer points, problems occurs after hundreds of lines. So it must be a very small problem. Can you figure it out? I would be very appreciated.

What I know about the unexpected result is they usually greater than the expected result. But in a point it require 7 when the program output 6. so I'm really confused. I even don't know in which case dose the problem occurs.

Additionally, the data point is guaranteed to be right. I've checked it by write Treap by myself.

EDIT

data range:

operations limit: 100000 times numeric limit: every number is in [-10000000,10000000]

0

There are 0 best solutions below