답안 #48441

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
48441 2018-05-13T14:35:33 Z ernestvw 입자 가속기 (IZhO11_collider) C++11
100 / 100
339 ms 56636 KB
#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;
}
# 결과 실행 시간 메모리 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