fork download
copy 
  1. ///      TANVIR HASAN
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define hello      printf("HELLO\n")
  7. #define uu         first
  8. #define vv         second
  9. #define pb         push_back
  10. #define mp         make_pair
  11. #define LL         long long
  12. #define inf        INT_MAX/3
  13. #define mod        1000000007ll
  14. #define PI         acos(-1.0)
  15. #define linf       (1ll<<60)-1
  16. #define pii        pair<int,int>
  17. #define vl        vector<LL>
  18. #define vi        vector<int>
  19. #define vs        vector<string>
  20. #define pii        pair<int,int>
  21.  
  22. #define ALL(A)     (A).begin(),(A).end()
  23. #define mset(a,v)     memset(a,v,sizeof a)
  24. #define setinf(ar)  memset(ar,126,sizeof ar)
  25. #define vsort(v)   sort(v.begin(),v.end())
  26.  
  27. #define FOR(I,A,B) for (__typeof (B) I = (A) ; I <= B ; ++I)
  28. #define rof(i, a, b)    for (__typeof (b)i = (b) ; i >= a ; --i)
  29. #define rep(I, n)       for (__typeof (n) I = 0 ; I < n ; ++I)
  30. #define per(i, n)       for (__typeof (n)i = (n-1) ; i >= 0 ; --i)
  31. #define forstl(I, s)    for (__typeof ((s).end ()) I = (s).begin (); I != (s).end (); ++I)
  32. #define rofstl(I, s)    for (__typeof ((s).end ()) I = (s).end ()-1; I != (s).begin (); --I)
  33.  
  34. #define Int ({int a; scanf("%d", &a); a;})
  35. #define I64 ({LL a; scanf("%I64d", &a); a;})
  36. #define Double ({double a; scanf("%lf", &a); a;})
  37. #define Char ({char a; scanf("%c", &a); a;})
  38. void FastIO()  {ios::sync_with_stdio(0);cin.tie(0);}
  39.  
  40. #define En "\n"
  41. #define round(a,b,n) ((a-1+b)% n + n)% n + 1  /// 1 base round,, a starting index ,,+b for left to right,,-b for left,|b| turn,,total n gor
  42. #define tata return 0
  43. ///           error////////////////////
  44.  
  45. #define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); puts(""); }
  46.  
  47. vector<string> split(const string& s, char c) {
  48.     vector<string> v;
  49.     stringstream ss(s);
  50.     string x;
  51.     while (getline(ss, x, c))
  52.         v.emplace_back(x);
  53.     return move(v);
  54. }
  55.  
  56. void err(vector<string>::iterator it) {}
  57. template<typename T, typename... Args>
  58. void err(vector<string>::iterator it, T a, Args... args) {
  59.     cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << "  ";
  60.     err(++it, args...);
  61. }
  62.  
  63.  
  64.  
  65. #define dbg(x) cout<<#x<<" : "<<x<<endl
  66. ///          eeerrrrooooooorrrrrrr //////////////////
  67.  
  68. template <class T> inline T bigmod(T p,T e,T M){LL ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;}return (T)ret;}
  69. template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
  70. template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}   // M is prime}
  71. template <class T> inline T bpow(T p,T e){LL ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p);p = (p * p);}return (T)ret;}
  72.  
  73.  
  74. #define EPS numeric_limits<double>::epsilon()
  75.  
  76.  
  77.  
  78. /// ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  79. ///                                      Let's do it                                                        ///
  80. ///                                      Let's try it                                                       ///
  81. /// ///////////////////////////////////////////////////////////////////////////////////////////////////////////
  82.  
  83.  
  84. #define maxN 1000005
  85.  
  86. struct bnode{
  87. 	int x, prior,size, lmn,rmn;
  88. 	bnode *l,*r;
  89. 	bnode(int _x){
  90. 		x=_x;
  91. 		prior=((rand()<<16)^rand());
  92. 		l=r=NULL;
  93. 		size=1;
  94.     rmn=lmn=inf;
  95. 	}
  96.   bnode(int _x,int p){
  97.     x=_x;
  98.     prior=p;
  99.     l=r=NULL;
  100.     size=1;
  101.   }
  102. 	bnode(){}
  103. };
  104. typedef bnode * bspnode;
  105. int sz(bspnode t){
  106.     return t?t->size:0;
  107. }
  108. void upd_sz(bspnode t){
  109.     if(t)t->size=sz(t->l)+1+sz(t->r);
  110. }
  111.  
  112. void push(bspnode t){
  113.   if(!t) return;
  114.   t->rmn=t->lmn=inf;
  115.   if(t->l) t->lmn= abs(t->x - t->l->x);
  116.   if(t->r) t->rmn= abs(t->x - t->r->x);
  117.   upd_sz(t);
  118. }
  119.  
  120. void bsplit(bspnode t,bspnode &l,bspnode &r,int value){
  121.     if(!t)return void(l=r=NULL);
  122.     push(t);
  123.     upd_sz(t);
  124.     if(value<t->x)//element at pos goes to "l"
  125.         bsplit(t->l,l,t->l,value),r=t;  
  126.     else 
  127.         bsplit(t->r,t->r,r,value),l=t;  
  128.  
  129.     upd_sz(l);  
  130.     upd_sz(r); 
  131.     push(l); 
  132.     push(r); 
  133.  
  134. }
  135. void bmerge(bspnode &t,bspnode l,bspnode r){ //l->leftarray,r->rightarray,t->resulting array
  136.  
  137.     upd_sz(l),upd_sz(r);
  138.     push(l),push(r);
  139.     if(!l || !r) t = l?l:r;
  140.     else{
  141.      if(l->prior>r->prior)bmerge(l->r,l->r,r),t=l;
  142.      else   bmerge(r->l,l,r->l),t=r;
  143.     }
  144.     upd_sz(t);
  145.     push(t);
  146.  
  147. }
  148.  
  149. void insert (bspnode &tb,int x){
  150. 	bspnode bl,br;
  151. 	bsplit(tb,bl,br,x-1);
  152. 	bmerge(bl,bl,new bnode(x));
  153. 	bmerge(tb,bl,br);
  154.  
  155. }
  156. void output(bspnode t){
  157. 	if(!t) return;
  158. 	output(t->l);
  159. 	printf("%d  ",t->x);
  160. 	output(t->r);
  161. }
  162.  
  163. bspnode unite(bspnode l,bspnode r){
  164. 	bspnode ret,less,grt;
  165. 	if(!l ||!r) return l?l:r;
  166.   upd_sz(l),upd_sz(r);
  167. 	if(l->prior < r->prior) swap(l,r);
  168. 	bsplit(r,less,grt,l->x);
  169. 	ret=new bnode(l->x,l->prior);
  170. 	ret->l=unite(l->l,less);
  171. 	ret->r=unite(l->r,grt);
  172.   upd_sz(ret);
  173. 	return ret;
  174.  
  175. }
  176. /*
  177.   void unite (pnode &t,pnode l, pnode r) {
  178.     if (!l || !r) return void(t = l ? l : r);
  179.     if (l->prior < r->prior) swap (l, r);
  180.     pnode lt, rt;
  181.     split (r,lt, rt,l->val);
  182.     unite (l->l,l->l, lt);
  183.     unite (l->r,l->r, rt);
  184.     t=l;upd_sz(t);
  185. }*/
  186. int lmn,rmn;
  187. int getKth(bspnode t,int k){
  188.     if(!t) return inf;
  189.     upd_sz(t);
  190.     if(k==sz(t->l)+1) {lmn=t->lmn,rmn=t->rmn;return t->x;}
  191.     if(sz(t->l)<k){
  192.       k-=sz(t->l)+1;
  193.       getKth(t->r,k);
  194.     }
  195.     else getKth(t->l,k);
  196. }
  197.  
  198. void del(bspnode &t,int x){
  199.     if(!t) return;
  200.     upd_sz(t);
  201.     bspnode less,grt,midam;
  202.     bsplit(t,less,grt,x-1);
  203.     bsplit(grt,midam,grt,x); //equal and less
  204.     bmerge(t,less,grt);
  205.     upd_sz(t);
  206. }
  207.  
  208.  
  209.  
  210. void split(bspnode t,bspnode &l,bspnode &r,int pos,int add=0){
  211.     if(!t)return void(l=r=NULL);
  212.    push(t);
  213.     int curr_pos = add + sz(t->l);
  214.     if(pos<=curr_pos)//element at pos goes to "l"
  215.         split(t->l,l,t->l,pos,add),r=t;  
  216.     else 
  217.         split(t->r,t->r,r,pos,curr_pos+1),l=t;  
  218.  
  219.   push(l);
  220.   push(r);
  221.  
  222. }
  223.  
  224. //////////////
  225.  
  226.  
  227. bspnode root;
  228. char cd[30];
  229. int val;
  230.  
  231. int main(){
  232.  // freopen("in.txt","r",stdin);
  233.    int n=Int;
  234.    while(n--){
  235.  
  236.     scanf(" %s %d",cd,&val);
  237.     if(cd[0]=='I'){
  238.  
  239.       insert(root,val);
  240.     }
  241.     else if(cd[0]=='D'){
  242.       del(root,val);
  243.  
  244.     }
  245.     else if(cd[0]=='X'){
  246.  
  247.       int val2=Int+1;
  248.       val++;
  249.       if(val==val2) {cout<<-1<<En;continue;}
  250.       int m=getKth(root,val);
  251.       int k=getKth(root,val2);
  252.       //error(m,k);
  253.       cout<<abs(k-m)<<En;
  254.  
  255.     }else if(cd[0]=='N'){
  256.  
  257.       val++;
  258.       int val2=Int+1;
  259.       if(val==val2) {cout<<-1<<En;continue;}
  260.       int mid=(val+val2)>>1;
  261.       if(val2-val==1){
  262.         int m= abs(getKth(root,val2) -getKth(root,val));
  263.         cout<<m<<En;
  264.         continue;
  265.       }
  266.         bspnode less,grt,tmp;
  267.         split(root,less,grt,val-1+1);
  268.         split(grt,grt,tmp,val2-val+1-1);
  269.         int mn=inf;
  270.         if(grt)
  271.          mn=min(grt->lmn,grt->rmn);
  272.         bmerge(grt,grt,tmp);
  273.         bmerge(root,less,grt);
  274.         getKth(root,val);
  275.         mn=min(mn,rmn);
  276.         getKth(root,val2);
  277.         mn=min(mn,lmn);
  278.         cout<<mn<<En;        
  279.  
  280.  
  281.     }
  282.   // output(root);
  283.    // hello;
  284.    }
  285.  
  286.  
  287.  
  288.  
  289.  
  290.  return 0;
  291. }
  292.  
  293.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
11
I 1
I 12
I 4
I 8
N 0 3
X 0 3
N 1 3
X 0 2
D 4
N 0 1
X 1 2
stdout
copy 
4
11
4
7
7
4
https://ideone.com/LJ6MXl
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!