Cod sursa(job #2381231)

Utilizator toonewbieAbutalib Namazov toonewbie Data 16 martie 2019 12:23:21
Problema Secv8 Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(100);

struct node {
    node *l, *r;
    int val, pr, sz, rev;
    node(int x = 0) : l(0), r(0), val(x), pr(rng()), sz(1), rev(0) {}
} *root, *lft, *rgt, *mmid;

typedef node* pnode;

void reset() {
    lft = rgt = mmid = new node();
    //lft = rgt = mmid = 0;
}

int sz(pnode v) {
    return v ? v -> sz : 0;
}
void pull(pnode &v) {
    if (v) v -> sz = sz(v -> l) + sz(v -> r) + 1;
}
void rev(pnode &v) {
    if (v) v -> rev ^= 1;
}
void push(pnode v) {
    if (v && v -> rev) {
        v -> rev = 0;
        swap(v -> l, v -> r);
        rev(v -> l), rev(v -> r);
    }
}

void merge(pnode &v, pnode l, pnode r) {
    push(l), push(r);
    if (!l || !r) {
        v = l ? l : r;
    } else if (l -> pr > r -> pr) {
        merge(l -> r, l -> r, r);
        v = l;
    } else {
        merge(r -> l, l, r -> l);
        v = r;
    }
    pull(v);
}

void split(pnode v, pnode &l, pnode &r, int key) {
    if (!v) return void(l = r = 0);
    push(v);
    if (key <= sz(v -> l)) {
        split(v -> l, l, v -> l, key);
        r = v;
    } else {
        split(v -> r, v -> r, r, key - sz(v -> l) - 1);
        l = v;
    }
    pull(v);
}

void insert(int pos, int val) {
    reset();
    split(root, lft, rgt, pos - 1);
    mmid -> val = val;
    merge(root, lft, mmid);
    merge(root, root, rgt);
}
void erase(int i, int j) {
    reset();
    split(root, lft, rgt, i - 1);
    split(rgt, mmid, rgt, j - i + 1);
    merge(root, lft, rgt);
}

void reverse(int i, int j) {
    reset();
    split(root, lft, rgt, i - 1);
    split(root, mmid, rgt, j - i + 1);
    rev(mmid);
    merge(root, lft, mmid);
    merge(root, root, rgt);
}

int get(int i) {
    reset();
    split(root, lft, rgt, i - 1);
    split(rgt, mmid, rgt, 1);
    int res = mmid -> val;
    merge(root, lft, mmid);
    merge(root, root, rgt);
    return res;
}
int main() {
    freopen("secv8.in", "r", stdin);
    freopen("secv8.out", "w", stdout);
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int q, x, y; char c;
    cin >> q >> x;
    cin >> c >> x >> y;
    root = new node(y); q--;
    int n = 1;
    while (q --) {
        cin >> c;
        if (c == 'I') {
            cin >> x >> y;
            n++, insert(x, y);
        } else if (c == 'A') {
            cin >> x;
            cout << get(x) << endl; //cout << flush;
        } else if (c == 'R') {
            cin >> x >> y;
            reverse(x, y);
        } else if (c == 'D') {
            cin >> x >> y;
            n -= y - x + 1, erase(x, y);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << get(i) << " ";
    }
    cout << endl;
    return 0;
}