Submission #38773

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
38773	2018-01-06T13:11:48 Z	Abelyan	Collider (IZhO11_collider)	C++14	100 / 100	533 ms	50544 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(7235);
    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	0 ms	3156 KB	Output is correct
2	Correct	16 ms	3552 KB	Output is correct
3	Correct	93 ms	8040 KB	Output is correct
4	Correct	293 ms	40776 KB	Output is correct
5	Correct	306 ms	40908 KB	Output is correct
6	Correct	403 ms	45792 KB	Output is correct
7	Correct	456 ms	50412 KB	Output is correct
8	Correct	336 ms	50148 KB	Output is correct
9	Correct	533 ms	50544 KB	Output is correct
10	Correct	439 ms	50412 KB	Output is correct