Submission #89895

#	Time	Username	Problem	Language	Result	Execution time	Memory
89895		popovicirobert	Collider (IZhO11_collider)	C++14	100 / 100	277 ms	56712 KiB

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 (stderr)

collider.cpp: In function 'int main()':
collider.cpp:116:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin >> str + 1;
            ~~~~^~~

• Subtask 1: 100 / 100