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.     bool getDir(pnode p,pnode x)
  14.     {
  15.         return p->c[1]==x;
  16.     }
  17.     void setLink(pnode x,pnode y,int d)
  18.     {
  19.         x->c[d]=y;
  20.         y->p=x;
  21.     }
  22.     void update(pnode u)
  23.     {
  24.         u->sz=1+u->c[0]->sz+u->c[1]->sz;
  25.         u->mx=max(u->val,max(u->c[0]->mx,u->c[1]->mx));
  26.     }
  27.     void rotate(pnode y,bool d)
  28.     {
  29.         pnode x=y->c[d],z=y->p;
  30.         setLink(y,x->c[d^1],d);
  31.         setLink(x,y,d^1);
  32.         setLink(z,x,getDir(z,y));
  33.         update(x);update(y);
  34.     }
  35.     void splay(pnode x)
  36.     {
  37.         while(x->p!=null)
  38.         {
  39.             pnode y=x->p,z=y->p;
  40.             int dy=getDir(y,x),dz=getDir(z,y);
  41.             if(z==null)
  42.                 rotate(y,dy);
  43.             else if(dy==dz)
  44.                 rotate(z,dz),rotate(y,dy);
  45.             else
  46.                 rotate(y,dy),rotate(z,dz);
  47.         }
  48.     }
  49.     pnode get(pnode u,int key,int add)
  50.     {
  51.         while(1)
  52.         {
  53.             int rank=1+add+u->c[0]->sz;
  54.             if(rank==key)
  55.             {
  56.                 splay(u);
  57.                 return u;
  58.             }
  59.             else if(rank<key)
  60.             {
  61.                 add=rank;
  62.                 u=u->c[1];
  63.             }
  64.             else
  65.                 u=u->c[0];
  66.         }
  67.     }
  68.     void split(pnode u,pnode &l,pnode &r,int key,int add)
  69.     {
  70.         if(key==add)
  71.         {
  72.             l=null;
  73.             r=u;
  74.         }
  75.         else
  76.         {
  77.             l=get(u,key,add);
  78.             r=l->c[1];
  79.             l->c[1]=r->p=null;
  80.             update(l);
  81.         }
  82.     }
  83.     int query(pnode u,int l,int r,int x,int y)
  84.     {
  85.         if(x>r || y<l)
  86.             return -1e9-9;
  87.         if(x<=l && r<=y)
  88.             return u->mx;
  89.         int rank=l+u->c[0]->sz;
  90.         int ret=-1e9-9;
  91.         if(x<=rank && rank<=y)
  92.             ret=u->val;
  93.         ret=max(ret,query(u->c[0],l,rank-1,x,y));
  94.         ret=max(ret,query(u->c[1],rank+1,r,x,y));
  95.         return ret;
  96.     }
  97.     Node buff[100005];
  98.     pnode ptr=buff;
  99.     pnode newNode()
  100.     {
  101.         return ++ptr;
  102.     }
  103. }   
  104. using namespace Splay;
  105. int main()
  106. {
  107.     null= newNode();
  108.     null->val=null->mx=-1e9-9;
  109.     null->sz=0;
  110.     null->c[0]=null->c[1]=null->p=null;
  111.     int m;
  112.     scanf("%d\n",&m);
  113.     pnode root=null;
  114.     while(m--)
  115.     {
  116.         char ty;
  117.         int x,y;
  118.         scanf("%c %d %d\n",&ty,&x,&y);
  119.         if(ty=='A')
  120.         {
  121.             pnode a,b;
  122.             split(root,a,b,y-1,0);
  123.             root=newNode();
  124.             root->val=root->mx=x;
  125.             root->sz=1;
  126.             root->c[0]=a;
  127.             root->c[1]=b;
  128.             root->p=null;
  129.             update(root);
  130.             a->p=b->p=root;
  131.         }
  132.         else if(ty=='Q')
  133.         {
  134.             printf("%d\n",query(root,1,root->sz,x,y));
  135.         }
  136.         else
  137.             assert(0);
  138.     }
  139. }
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:137: int main(): Assertion `0' failed.
https://ideone.com/qMBy42
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!