oj.uz

Submission #115505

# Submission time Handle Problem Language Result Execution time Memory
115505 2019-06-08T01:02:20 Z thebes Collider (IZhO11_collider) C++14
100 / 100
 238 ms 49516 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 10 ms 512 KB Output is correct
3 Correct 30 ms 5240 KB Output is correct
4 Correct 147 ms 39556 KB Output is correct
5 Correct 173 ms 39600 KB Output is correct
6 Correct 195 ms 44588 KB Output is correct
7 Correct 213 ms 49512 KB Output is correct
8 Correct 187 ms 49512 KB Output is correct
9 Correct 238 ms 49516 KB Output is correct
10 Correct 206 ms 49512 KB Output is correct