fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<ctime>
  4. #include<algorithm>
  5. #define SIZE(t) ((t)?(t)->size:0) 
  6. #define MAXNUM(t) ((t)?(t)->mn:0) 
  7. using namespace std;
  8. struct Treap{
  9.     Treap *L,*R;
  10.     int size,num,mn;
  11.     Treap(int _num){
  12.         num=mn=_num;
  13.         L=R=NULL; 
  14.         size=1;
  15.     }
  16.     void up(){
  17.         size=SIZE(L)+SIZE(R)+1;
  18.         mn=max(num,max(MAXNUM(L),MAXNUM(R)));
  19.     }
  20. }*tr;
  21. Treap *merge(Treap *a,Treap *b)
  22. {
  23.     if(!a||!b) return a?a:b;
  24.     if(rand()%2){
  25.         a->R=merge(a->R,b);
  26.         a->up();
  27.         return a;
  28.     }else{
  29.         b->L=merge(a,b->L);
  30.         b->up();
  31.         return b;
  32.     }
  33. }
  34. void split(Treap *tr,Treap *&a,Treap *&b,int k)
  35. {
  36.     if(k==0){
  37.         a=NULL; b=tr;
  38.     }else{
  39.         if(SIZE(tr->L)>=k){
  40.             b=tr;
  41.             split(b->L,a,b->L,k);
  42.             b->up();
  43.         }else{
  44.             a=tr;
  45.             split(a->R,a->R,b,k-SIZE(a->L)-1);
  46.             a->up();
  47.         }
  48.     }
  49. }
  50. int main()
  51. {
  52.     srand(time(NULL));
  53.     int n,q;
  54.     scanf("%d %d",&n,&q);
  55.     int tmp;
  56.     scanf("%d",&tmp);
  57.     tr=new Treap(tmp);
  58.     for(int i=1;i<n;i++){
  59.         scanf("%d",&tmp);
  60.         tr=merge(tr,new Treap(tmp));
  61.     }
  62.  
  63.     for(int i=0;i<q;i++)
  64.     {
  65.         int a,b,c;
  66.         scanf("%d %d %d",&a,&b,&c);
  67.         if(a==1)
  68.         {
  69.             Treap *x,*y,*z;
  70.             split(tr,x,y,b-1);
  71.             split(y,y,z,1);
  72.             y=new Treap(c);
  73.             x=merge(x,y);
  74.             tr=merge(x,z);
  75.         }
  76.         else
  77.         {
  78.             Treap *x,*y,*z;
  79.             split(tr,y,z,c);
  80.             split(y,x,y,b-1);
  81.             printf("%d\n",MAXNUM(y));
  82.             x=merge(x,y);
  83.             tr=merge(x,z);
  84.         }
  85.     }
  86. }
Time limit exceeded #stdin #stdout 5s 240960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Tv3G1H
language:
C++14 (gcc 8.3)
created:
9 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!