Submission #89895

# Submission time Handle Problem Language Result Execution time Memory
89895 2018-12-18T19:37:04 Z popovicirobert Collider (IZhO11_collider) C++14
100 / 100
277 ms 56712 KB
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 1e6;

char str[MAXN + 1];

typedef struct Treap *T;
typedef pair <T, T> PTT;

T root, NIL;

struct Treap {
    Treap *left, *right;
    char ch;
    int prio, sz;
    Treap(char _ch) {
        left = right = NIL;
        ch = _ch;
        prio = rand();
        sz = 1;
    }
};

inline void refresh(T nod) {
    nod -> sz = nod -> left -> sz + nod -> right -> sz + 1;
}

T join(T a, T b) {
    if(a == NIL) {
        return b;
    }
    if(b == NIL) {
        return a;
    }
    if(a -> prio >= b -> prio) {
        a -> right = join(a -> right, b);
        refresh(a);
        return a;
    }
    b -> left = join(a, b -> left);
    refresh(b);
    return b;
}

PTT split(T nod, int sz) {
    if(nod == NIL) {
        return {NIL, NIL};
    }
    if(nod -> left -> sz >= sz) {
        PTT aux = split(nod -> left, sz);
        nod -> left = aux.second;
        refresh(nod);
        return {aux.first, nod};
    }
    if(nod -> left -> sz + 1 == sz) {
        PTT aux = {nod, nod -> right};
        nod -> right = NIL;
        refresh(nod);
        return aux;
    }
    PTT aux = split(nod -> right, sz - nod -> left -> sz - 1);
    nod -> right = aux.first;
    refresh(nod);
    return {nod, aux.second};
}

T ins(T nod, int sz, char ch) {
    PTT aux = split(nod, sz - 1);
    T cur = new Treap(ch);
    return join(aux.first, join(cur, aux.second));
}

T del(T nod, int sz, char &cur) {
    PTT aux1 = split(nod, sz - 1);
    PTT aux2 = split(aux1.second, 1);
    cur = aux2.first -> ch;
    return join(aux1.first, aux2.second);
}

char query(T nod, int sz) {
    if(nod -> left -> sz + 1 == sz) {
        return nod -> ch;
    }
    if(nod -> left -> sz >= sz) {
        return query(nod -> left, sz);
    }
    return query(nod -> right, sz - nod -> left -> sz - 1);
}

/*void dfs(T nod) {
    if(nod == NIL) {
        return ;
    }

    dfs(nod -> left);
    cerr << nod -> ch << " ";
    dfs(nod -> right);
}*/

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    srand(time(NULL));
    cin >> n >> m;
    cin >> str + 1;
    NIL = new Treap(0);
    NIL -> left = NIL -> right = NIL;
    NIL -> sz = NIL -> prio = 0;
    root = NIL;
    for(i = 1; i <= n; i++) {
        root = ins(root, i, str[i]);
    }
    for(i = 1; i <= m; i++) {
        char ch;
        cin >> ch;
        if(ch == 'a') {
            int p1, p2;
            cin >> p1 >> p2;
            char cur;
            root = del(root, p1, cur);
            root = ins(root, p2, cur);
        }
        else {
            int p;
            cin >> p;
            cout << query(root, p) << "\n";
        }
        //dfs(root);
        //cerr << "\n";
    }
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

collider.cpp: In function 'int main()':
collider.cpp:116:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin >> str + 1;
            ~~~~^~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 10 ms 864 KB Output is correct
3 Correct 32 ms 5568 KB Output is correct
4 Correct 202 ms 40148 KB Output is correct
5 Correct 206 ms 41292 KB Output is correct
6 Correct 236 ms 47236 KB Output is correct
7 Correct 273 ms 53108 KB Output is correct
8 Correct 244 ms 53992 KB Output is correct
9 Correct 277 ms 55640 KB Output is correct
10 Correct 233 ms 56712 KB Output is correct