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. // void display(pnode u,int add=0)
  71. // {
  72. //     if(u)
  73. //     {
  74. //         int rank=add+1+sz(u->l);
  75. //         cout<<"At "<<rank<<endl;
  76. //         cout<<"Going left"<<endl;
  77. //         display(u->l,add);
  78. //         cout<<"Back at "<<rank<<endl;
  79. //         cout<<"Going right"<<endl;
  80. //         display(u->r,rank);
  81. //     }
  82. //     cout<<"Nothing"<<endl;
  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.     while(m--)
  93.     {
  94.         char ty;
  95.         int x,y;
  96.         scanf("%c %d %d\n",&ty,&x,&y);
  97.         if(ty=='A')
  98.         {
  99.             pnode l,r;
  100.             split(root,l,r,y-1,0);
  101.             merge(l,l,init(x));
  102.             merge(root,l,r);
  103.         }
  104.         else if(ty=='Q')
  105.         {
  106.             pnode A,B,C,temp;
  107.             split(root,A,temp,x-1,0);
  108.             split(temp,B,C,y,x-1);
  109.             printf("%d\n",B->mx);
  110.             merge(temp,B,C);
  111.             merge(root,A,temp);
  112.         }   
  113.         else
  114.             assert(0);
  115.     }
  116. }
Runtime error #stdin #stdout #stderr 0s 5808KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
prog: prog.cpp:114: int main(): Assertion `0' failed.
https://ideone.com/cIRGyE
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!