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:
- insert number
x
- delete number
x
- look up number
x
's order("order" refers to the number of the elements smaller than this number+1) - look up for the number which order is
x
- look up for number
x
's prefix - 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]