Submission #48441

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
48441	2018-05-13T14:35:33 Z	ernestvw	Collider (IZhO11_collider)	C++11	100 / 100	339 ms	56636 KB

collider

#include <bits/stdc++.h>
using namespace std;
 
struct node{
    char val;
    int prior, sz;
    node *l,*r;
    node(char _val='!'):val(_val),prior(rand()),sz(1),l(NULL),r(NULL){}
};
 
int Get_Size(node *T){
    return T ? T->sz : 0;
}
 
void Recalc(node *&T){
    if (T){
        T->sz=Get_Size(T->l)+Get_Size(T->r)+1;
    }
}
 
void Merge(node *&T,node *L,node *R){
    if (!L){
        T=R;
        return;
    }
    if (!R){
        T=L;
        return;
    }
    if (L->prior>R->prior){
        Merge(L->r,L->r,R);
        T=L;
    }
    else{
        Merge(R->l,L,R->l);
        T=R;
    }
    Recalc(T);
    Recalc(L);
    Recalc(R);
}
 
void Split(node *T,node *&L,node *&R,int x){
    if (!T){
        R=L=NULL;
        return;
    }
    int index=Get_Size(T->l)+1;
    if (index<=x){
        Split(T->r,T->r,R,x-index);
        L=T;
        Recalc(L);
        Recalc(R);
    }
    else{
        Split(T->l,L,T->l,x);
        R=T;
        Recalc(R);
        Recalc(L);
    }
}
 
void Insert(node *&T,char k,int x){
    node *ptr=new node(k);
    node *L,*R;
    Split(T,L,R,x-1);
    Merge(T,L,ptr);
    Merge(T,T,R);
}
 
void Erase(node *&T,int x){
    node *ptr,*L,*R;
    Split(T,L,R,x);
    Split(L,L,ptr,x-1);
    Merge(T,L,R);
}
 
char Get(node *T,int k){
    int index=Get_Size(T->l)+1;
    if (index==k){
        return T->val;
    }
    if (index<k){
        return Get(T->r,k-index);
    }
    return Get(T->l,k);
}
 
void Teleport(node *&T,int l,int r){
    char k=Get(T,l);
    Erase(T,l);
    Insert(T,k,r);
}
 
void build (node *&T,char a[],int n){
    for (int i=1;i<=n;i++){
        Insert(T,a[i],i);
    }
}
 
char c[1000006];
 
int main()
{
    ios_base::sync_with_stdio(false);
    srand(2535);
    node *T=NULL;
    int n,q;
    cin>>n>>q;
    for (int i=1;i<=n;i++){
        cin>>c[i];
    }
    build(T,c,n);
    for (int i=0;i<q;i++){
        char k;
        cin>>k;
        if (k=='a'){
            int l,r;
            cin>>l>>r;
            Teleport(T,l,r);
        }
        else{
            int k;
            cin>>k;
            cout<<Get(T,k)<<endl;
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	16 ms	880 KB	Output is correct
3	Correct	40 ms	5808 KB	Output is correct
4	Correct	233 ms	40140 KB	Output is correct
5	Correct	263 ms	41324 KB	Output is correct
6	Correct	293 ms	47208 KB	Output is correct
7	Correct	325 ms	53256 KB	Output is correct
8	Correct	289 ms	54048 KB	Output is correct
9	Correct	338 ms	55592 KB	Output is correct
10	Correct	339 ms	56636 KB	Output is correct