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

collider

#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;
            ~~~~^~~

Subtask #1

100.0 / 100.0

#	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