# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
38775 | Abelyan | Collider (IZhO11_collider) | C++14 | 496 ms | 50544 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(5431);
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |