fork download
copy 
  1. //Pranet Verma
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. namespace Splay
  5. {
  6.     typedef struct Node* pnode;
  7.     pnode null;
  8.     struct Node
  9.     {
  10.         int val,mx,sz;
  11.         pnode c[2],p;
  12.     };
  13.     // void display(pnode u)
  14.     // {
  15.     //     if(u==null)
  16.     //         return;
  17.     //     display(u->c[0]);
  18.     //     cout<<u->val<<" "<<endl;
  19.     //     display(u->c[1]);        
  20.     // }
  21.     bool getDir(pnode p,pnode x)
  22.     {
  23.         return p->c[1]==x;
  24.     }
  25.     void setLink(pnode x,pnode y,int d)
  26.     {
  27.         if(x!=null)
  28.             x->c[d]=y;
  29.         if(y!=null)
  30.             y->p=x;
  31.     }
  32.     void update(pnode u)
  33.     {
  34.         if(u==null)
  35.             return;
  36.         u->sz=1+u->c[0]->sz+u->c[1]->sz;
  37.         u->mx=max(u->val,max(u->c[0]->mx,u->c[1]->mx));
  38.     }
  39.     void rotate(pnode y,bool d)
  40.     {
  41.         pnode x=y->c[d],z=y->p;
  42.         setLink(y,x->c[d^1],d);
  43.         setLink(x,y,d^1);
  44.         setLink(z,x,getDir(z,y));
  45.         update(x);update(y);
  46.     }
  47.     void splay(pnode x)
  48.     {
  49.         while(x->p!=null)
  50.         {
  51.             pnode y=x->p,z=y->p;
  52.             int dy=getDir(y,x),dz=getDir(z,y);
  53.             if(z==null)
  54.                 rotate(y,dy);
  55.             else if(dy==dz)
  56.                 rotate(z,dz),rotate(y,dy);
  57.             else
  58.                 rotate(y,dy),rotate(z,dz);
  59.         }
  60.     }
  61.     pnode get(pnode u,int key,int add)
  62.     {
  63.         while(1)
  64.         {
  65.             int rank=1+add+u->c[0]->sz;
  66.             if(rank==key)
  67.             {
  68.                 splay(u);
  69.                 return u;
  70.             }
  71.             else if(rank<key)
  72.             {
  73.                 add=rank;
  74.                 u=u->c[1];
  75.             }
  76.             else
  77.                 u=u->c[0];
  78.         }
  79.     }
  80.     void split(pnode u,pnode &l,pnode &r,int key,int add)
  81.     {
  82.         if(key==add)
  83.         {
  84.             l=null;
  85.             r=u;
  86.         }
  87.         else
  88.         {
  89.             l=get(u,key,add);
  90.             r=l->c[1];
  91.             l->c[1]=r->p=null;
  92.             update(l);
  93.         }
  94.     }
  95.     void merge(pnode &u,pnode x,pnode y)
  96.     {
  97.         if(x==null)
  98.             u=y;
  99.         else if(y==null)
  100.             u=x;
  101.         else
  102.         {
  103.             u=get(x,x->sz,0);
  104.             setLink(u,y,1);
  105.             update(u);
  106.         }
  107.     }
  108.     const int MAXN=100005;
  109.     Node buff[MAXN],*ptr=buff;
  110.     pnode newNode()
  111.     {
  112.         return ++ptr;
  113.     }
  114. }   
  115. using namespace Splay;
  116. int main()
  117. {
  118.     null= newNode();
  119.     null->val=null->mx=-1e9-9;
  120.     null->sz=0;
  121.     null->c[0]=null->c[1]=null->p=null;
  122.     int m;
  123.     scanf("%d\n",&m);
  124.     pnode root=null;
  125.     while(m--)
  126.     {
  127.         char ty;
  128.         int x,y;
  129.         scanf("%c %d %d\n",&ty,&x,&y);
  130.         if(ty=='A')
  131.         {
  132.             pnode a,b;
  133.             split(root,a,b,y-1,0);
  134.             root=newNode();
  135.             root->val=root->mx=x;
  136.             root->sz=1;
  137.             root->c[0]=a;
  138.             root->c[1]=b;
  139.             root->p=null;
  140.             // update(root);
  141.             a->p=b->p=root;
  142.         }
  143.         else if(ty=='Q')
  144.         {
  145.             pnode a,b,c;
  146.             split(root,a,b,x-1,0);
  147.             split(b,b,c,y,a->sz);
  148.             printf("%d\n",b->mx);
  149.             merge(b,b,c);
  150.             merge(root,a,b);
  151.         }   
  152.         else
  153.             assert(0);
  154.     }
  155. }
Runtime error #stdin #stdout #stderr 0s 5808KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:153: int main(): Assertion `0' failed.
https://ideone.com/4VV06y
language:
C++ (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!