Submission #115505

#	Time	Username	Problem	Language	Result	Execution time	Memory
115505		thebes	Collider (IZhO11_collider)	C++14	100 / 100	238 ms	49516 KiB

collider

#include <bits/stdc++.h>
using namespace std;

struct nd{
    char ch; int sz, p; nd *l, *r;
    nd(char c):ch(c),sz(1),p(rand()),l(0),r(0){}
}*rt;

inline int sz(nd *n){return n?n->sz:0;}
inline void upd(nd *&n){if(n)n->sz=sz(n->l)+sz(n->r)+1;}
void split(nd *n,nd *&l,nd *&r,int k){
    if(!n) l=r=NULL;
    else if(sz(n->l)+1>k) split(n->l,l,n->l,k),r=n;
    else split(n->r,n->r,r,k-sz(n->l)-1),l=n;
    upd(n);
}
void mrg(nd *&n,nd *l,nd *r){
    if(!l||!r) n=l?l:r;
    else if(l->p>r->p) mrg(l->r,l->r,r),n=l;
    else mrg(r->l,l,r->l),n=r;
    upd(n);
}
char qu(nd *n,int k){
    if(sz(n->l)+1==k) return n->ch;
    else if(sz(n->l)+1<k) return qu(n->r,k-sz(n->l)-1);
    else return qu(n->l,k);
}

int n, m, i, x, y;
char ch; string s; nd *l, *r, *t, *a;

int main(){
    cin >> n >> m >> s;
    for(i=0;i<s.size();i++) mrg(rt,rt,new nd(s[i]));
    for(;m;m--){
        scanf(" %c%d",&ch,&x);
        if(ch=='q') printf("%c\n",qu(rt,x));
        else{
            scanf("%d",&y);
            split(rt, a, r, x);
            split(a, l, t, x-1);
            mrg(rt, l, r);
            split(rt, l, r, y-1);
            mrg(a, l, t);
            mrg(rt, a, r);
        }
    }
    return 0;
}

Compilation message (stderr)

collider.cpp: In function 'int main()':
collider.cpp:34:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<s.size();i++) mrg(rt,rt,new nd(s[i]));
             ~^~~~~~~~~
collider.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c%d",&ch,&x);
         ~~~~~^~~~~~~~~~~~~~~~
collider.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&y);
             ~~~~~^~~~~~~~~

• Subtask 1: 100 / 100