Cod sursa(job #1689210)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 14 aprilie 2016 01:45:17
Problema Secv8 Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include <bits/stdc++.h>

using namespace std;

inline int Random() {
    return (rand() << 16) ^ rand();
}

struct Node {
    int v, pr, sz;
    bool rev;
    Node *l, *r;

    Node(int v = 0, int pr = 0, int sz = 0, Node *l = 0, Node *r = 0):
        v(v),
        pr(pr),
        sz(sz),
        rev(0),
        l(l),
        r(r) {
    }
} *T, *nil;

void Update(Node *node) {
    if (node == nil)
        return;
    if (node->rev) {
        node->rev = 0;
        node->l->rev ^= 1;
        node->r->rev ^= 1;
        swap(node->l, node->r);
    }
    node->sz = node->l->sz + node->r->sz + 1;
}

pair<Node *, Node *> Split(Node *node, int pos) {
    if (node == nil)
        return {nil, nil};

    Update(node);
    if (pos <= node->l->sz) {
        auto split = Split(node->l, pos);
        node->l = split.second;
        split.second = node;
        Update(node);
        return split;
    } else {
        auto split = Split(node->r, pos - 1 - node->l->sz);
        node->r = split.first;
        split.first = node;
        Update(node);
        return split;
    }
}

Node *Unite(Node *left, Node *right) {
    if (left == nil)
        return right;
    if (right == nil)
        return left;

    Update(left);
    Update(right);
    if (left->pr >= right->pr) {
        left->r = Unite(left->r, right);
        Update(left);
        return left;
    } else {
        right->l = Unite(left, right->l);
        Update(right);
        return right;
    }
}

int kth(Node *node, int pos) {
    if (node == nil)
        return -1;

    Update(node);
    if (pos == node->l->sz + 1)
        return node->v;
    if (pos <= node->l->sz)
        return kth(node->l, pos);
    return kth(node->r, pos - 1 - node->l->sz);
}

void Print(Node *node, ofstream &cout) {
    if (node == nil)
        return;
    Print(node->l, cout);
    cout << node->v << ' ';
    Print(node->r, cout);
}

int main() {
    ifstream cin("secv8.in");
    ofstream cout("secv8.out");

    srand(time(0));

    int i, j;
    T = nil = new Node(-1, -1);
    nil->l = nil->r = nil;

    int M, useless;
    cin >> M >> useless;
    while (M--) {
        char type;
        int k, e;
        cin >> type;
        if (type == 'I') {
            cin >> k >> e;
            auto split = Split(T, k - 1);
            Node *temp = new Node(e, Random(), 1, nil, nil);
            T = Unite(Unite(split.first, temp), split.second);
        } else if (type == 'A') {
            cin >> k;
            cout << kth(T, k) << '\n';
        } else if (type == 'R') {
            cin >> i >> j;
            auto split1 = Split(T, i - 1);
            auto split2 = Split(split1.second, j - i + 1);
            split2.first->rev ^= 1;
            T = Unite(Unite(split1.first, split2.first), split2.second);
        } else {
            cin >> i >> j;
            auto split1 = Split(T, i - 1);
            auto split2 = Split(split1.second, j - i + 1);
            T = Unite(split1.first, split2.second);
        }
    }

    Print(T, cout);
    cout << '\n';
    return 0;
}