fork download 
  1. //Pranet Verma
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef struct Node* pnode;
  5. struct Node
  6. {
  7.     pnode l,r;
  8.     int prior,cnt,val,mx;
  9. }tree[100005],*pool=tree,*null=tree;
  10. pnode init(int v)
  11. {
  12.     ++pool;
  13.     pool->prior=rand();
  14.     pool->val=v;
  15.     pool->l=null;
  16.     pool->r=null;
  17.     pool->cnt=0;
  18.     pool->mx=v;
  19.     return pool;
  20. }
  21. void update(pnode u)
  22. {
  23.     if(u!=null)
  24.     {
  25.         u->cnt=1+u->l->cnt+u->r->cnt;
  26.         u->mx=max(u->val,max(u->l->mx,u->r->mx));
  27.     }
  28. }
  29. void split(pnode u,pnode &l,pnode &r,int key,int add)
  30. {
  31.     if(u==null)
  32.         l=r=null;
  33.     else
  34.     {
  35.         int rank=add+1+u->l->cnt;
  36.         if(rank<=key)
  37.         {
  38.             split(u->r,u->r,r,key,rank);
  39.             l=u;
  40.         }
  41.         else
  42.         {
  43.             split(u->l,l,u->l,key,add);
  44.             r=u;
  45.         }
  46.     }
  47.     update(u);
  48. }
  49. void merge(pnode &u,pnode l,pnode r)
  50. {
  51.     if(l==null)
  52.         u=r;
  53.     else if(r==null)
  54.         u=l;
  55.     else
  56.     {
  57.         if(l->prior > r->prior)
  58.         {
  59.             merge(l->r,l->r,r);
  60.             u=l;
  61.         }
  62.         else
  63.         {
  64.             merge(r->l,l,r->l);
  65.             u=r;
  66.         }
  67.     }
  68.     update(u);
  69. }
  70. int query(pnode &u,int l,int r,int x,int y)
  71. {
  72.     if(x>r || y<l)
  73.         return -2e9;
  74.     if(x<=l && r<=y)
  75.         return u->mx;
  76.     int rank=l+u->l->cnt;
  77.     int ret=-2e9;
  78.     if(x<=rank && rank<=y)
  79.         ret=u->val;
  80.     ret=max(ret,query(u->l,l,rank-1,x,y));
  81.     ret=max(ret,query(u->r,rank+1,r,x,y));
  82.     return ret;
  83. }
  84. int main()
  85. {
  86.     null->l=null->r=null;
  87.     null->val=null->mx=-2e9;
  88.     null->cnt=0;
  89.     int m;
  90.     scanf("%d\n",&m);
  91.     pnode root=null;
  92.     int have=0;
  93.     while(m--)
  94.     {
  95.         char ty;
  96.         int x,y;
  97.         scanf("%c %d %d\n",&ty,&x,&y);
  98.         if(ty=='A')
  99.         {
  100.             pnode l,r;
  101.             split(root,l,r,y-1,0);
  102.             merge(l,l,init(x));
  103.             merge(root,l,r);
  104.             ++have;
  105.         }
  106.         else if(ty=='Q')
  107.             printf("%d\n",query(root,1,have,x,y));
  108.         else
  109.             assert(0);
  110.     }
  111. }
Runtime error #stdin #stdout #stderr 0s 5808KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
prog: prog.cpp:109: int main(): Assertion `0' failed.
https://ideone.com/TCKF76
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!