oj.uz

Submission #523217

# Submission time Handle Problem Language Result Execution time Memory
523217 2022-02-07T08:19:12 Z RaresFelix Collider (IZhO11_collider) C++17
100 / 100
 174 ms 49428 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 15 ms 332 KB Output is correct
3 Correct 22 ms 5152 KB Output is correct
4 Correct 113 ms 39472 KB Output is correct
5 Correct 128 ms 39468 KB Output is correct
6 Correct 150 ms 44448 KB Output is correct
7 Correct 163 ms 49348 KB Output is correct
8 Correct 136 ms 49168 KB Output is correct
9 Correct 174 ms 49428 KB Output is correct
10 Correct 155 ms 49228 KB Output is correct