Submission #37377

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
37377	2017-12-24T18:51:34 Z	alenam0161	Collider (IZhO11_collider)	C++14	100 / 100	306 ms	57908 KB

collider

#include <bits/stdc++.h>
#define ad push_back

using namespace std;
using ll = long long;
using ld = long double;
const int N = 1000*1000+7;
struct node{
   char val;
   int prior;
   int key;
   node *l,*r;
   node (char _Val='0'):val(_Val),prior(rand()),key(1),l(nullptr),r(nullptr){}
};
void printt(node *t,int rnk=0){
  if(t==nullptr)return;
  printt(t->l,rnk+1);
  cout<<rnk<<" -> LEVEL <-"<<t->val<<" "<<t->key<<" hi->"<<t->prior<<endl;
  printt(t->r,rnk+1);
}
int cnt(node *t){
   return t==nullptr ? 0:t->key;
}
void upd_cnt(node *&t){
  if(t!=nullptr){
    t->key=cnt(t->l)+cnt(t->r)+1;
  }
}
void split(node *t,node *&l,node *&r,int key){
   if(t==nullptr){
    l=r=nullptr;
    return;
   }
//   cout<<key<<" "<<t->val<<endl;
   if(key<=cnt(t->l)){
 //       cout<<"qta  "<<cnt(t->l)<<endl;
    split(t->l,l,t->l,key);
    r=t;
   }
   else{
    split(t->r,t->r,r,key-cnt(t->l)-1);
    l=t;
   }
   upd_cnt(t);
}
void merge(node *&t,node *l,node *r){
   if(l==nullptr||r==nullptr){
    t=l==nullptr ? r:l;
    return;
   }
   if(l->prior>r->prior){
    merge(l->r,l->r,r);t=l;
   }
   else{
    merge(r->l,l,r->l);t=r;
   }
   upd_cnt(t);
   upd_cnt(l);
   upd_cnt(r);
}

node *ma[N];
int main(){
  ios_base::sync_with_stdio(false);
//  freopen("G.in","r",stdin);
//  freopen("G.out","w",stdout);
  srand(5431);
  node *root=nullptr;
  int n,m;
  cin>>n>>m;
  string s;
  cin>>s;
  ma[0]=new node('$');
  for(int i=0;i<s.length();++i){
   ma[i+1]=new node(s[i]);
  }
  for(int i=1;i<=s.length();++i){
    merge(root,root,ma[i]);
    /*
    printt(root);
    cout<<"yes\n"<<endl;
    */
  }
 // printt(root);
  for(int i=1;i<=m;++i){
    char kind;
    cin>>kind;
    if(kind=='a'){
        int a,b;
        cin>>a>>b;
        node *l=nullptr,*r=nullptr,*cur=nullptr;
        if(a<b){
            split(root,root,r,b);
            split(root,root,l,a-1);
            split(l,cur,l,1);
            merge(root,root,l);
            merge(root,root,cur);
            merge(root,root,r);
      //      printt(root);
        }
        else if(a>b){
            swap(a,b);
            split(root,root,r,b-1);
            split(root,root,l,a-1);
            split(r,cur,r,1);
            merge(root,root,cur);
            merge(root,root,l);
            merge(root,root,r);
        }
    }
    else{
        int pos;
        cin>>pos;
        node *l=nullptr,*r=nullptr,*ta=nullptr,*tb=nullptr;
    //    cout<<pos<<endl;
        split(root,root,r,pos-1);
        split(r,l,r,1);
       /*
        cout<<"start"<<endl;
        printt(root);
        cout<<"QQQQ"<<endl;
        printt(l);
        cout<<"ZZZZ"<<endl;
        printt(r);
       */
        cout<<l->val<<endl;
        merge(r,l,r);
        merge(root,root,r);
    }
  }



  return 0;
}

Compilation message

collider.cpp: In function 'int main()':
collider.cpp:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.length();++i){
                ^
collider.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<=s.length();++i){
                ^
collider.cpp:114:37: warning: unused variable 'ta' [-Wunused-variable]
         node *l=nullptr,*r=nullptr,*ta=nullptr,*tb=nullptr;
                                     ^
collider.cpp:114:49: warning: unused variable 'tb' [-Wunused-variable]
         node *l=nullptr,*r=nullptr,*ta=nullptr,*tb=nullptr;
                                                 ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9992 KB	Output is correct
2	Correct	23 ms	9992 KB	Output is correct
3	Correct	46 ms	14764 KB	Output is correct
4	Correct	189 ms	48536 KB	Output is correct
5	Correct	216 ms	48536 KB	Output is correct
6	Correct	236 ms	53156 KB	Output is correct
7	Correct	293 ms	57908 KB	Output is correct
8	Correct	223 ms	57908 KB	Output is correct
9	Correct	306 ms	57908 KB	Output is correct
10	Correct	233 ms	57908 KB	Output is correct