Submission #523217

#	Time	Username	Problem	Language	Result	Execution time	Memory
523217		RaresFelix	Collider (IZhO11_collider)	C++17	100 / 100	174 ms	49428 KiB

collider

#include <bits/stdc++.h>
#define MN 1007171
#define INF 1000000000
using namespace std;

struct nod {
    char v;
    int c, p;
    nod *l, *r;
} *nil = new nod{0, 0, 0, 0, 0};

using ns = nod *;

struct pns {
    ns l, r;
};

ns mod_fiu(ns b, int s, ns f) {
    (s ? b->r : b->l) = f;
    b->c = 1 + b->l->c + b->r->c;
    return b;
}

ns join(ns a, ns b) {
    return a == nil ? b :
           b == nil ? a :
           (a->p > b->p) ? mod_fiu(a, 1, join(a->r, b)) :
           mod_fiu(b, 0, join(a, b->l));
}

pns split(ns a, int nr) {
    pns t;
    return a == nil ? pns{nil, nil} :
           (a->c <= nr) ? pns{a, nil} :
           !nr ? pns{nil, a} :
           (a->l->c >= nr) ? (t = split(a->l, nr), t.r = mod_fiu(a, 0, t.r), t) :
           (t = split(a->r, nr - a->l->c - 1), t.l = mod_fiu(a, 1, t.l), t);
}

void afis(ns a) {
    if(a == nil) return;
    afis(a->l);
    cout << a->v;
    afis(a->r);
}

ns root = nil;
int n, m;
char C[MN];
int main() {
    srand(time(0));
    cin >> n >> m >> (C+1);
    for(int i = 1; i <= n; ++i)
        root = join(root, new nod{C[i], 1, rand(), nil, nil});
    char tip;
    for(int i = 1, l, r; i <= m; ++i) {
        cin >> tip;
        if(tip == 'a') {
            cin >> l >> r;
            pns a = split(root, l - 1), b = split(a.r, 1);
            root = join(a.l, b.r);
//            cout << "\n";
//            afis(root);
//            cout << "\n";
            ns el = b.l;
            a = split(root, r - 1);
            root = join(join(a.l, el), a.r);
        } else {
            cin >> l;
            pns a = split(root, l-1), b = split(a.r, 1);
            cout << b.l->v << "\n";
            root = join(a.l, join(b.l, b.r));
        }
//        cout << "\nmain : ";
//        afis(root);
//        cout << "\n";
    }
}
/**
 * xxyyzxxzxzyyzyx
 * xxyyzxxzzxyyzyx
 *
 * xxyxyzxxzzxyyzy
 *
 * xxyxyzxxzxzyyzy
 *
 * xxyxyzxxzzxyyzy
 * xxyxyzxxzxzyyzy
*/

• Subtask 1: 100 / 100