Cod sursa(job #2700465)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 27 ianuarie 2021 19:23:43
Problema Secv8 Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.19 kb
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

ifstream fin("secv8.in");
ofstream fout("secv8.out");

const int MOD = 1e9 + 7;

struct Node{
    int cnt, val, priority;
    bool rev;
    Node * left, * right;

    Node(int val, int priority) {
        this -> rev = false;
        this -> cnt = 1;
        this -> val = val;
        this -> priority = priority;
        this -> left = NULL;
        this -> right = NULL;
    }
};

Node * root;

void lazy(Node *& currentNode) {
    if(currentNode && currentNode -> rev) {
        swap(currentNode -> left, currentNode -> right);
        currentNode -> rev = 0;

        if(currentNode -> left)
            currentNode -> left -> rev ^= 1;

        if(currentNode -> right)
            currentNode -> right -> rev ^= 1;
    }
}

void print(Node * currentNode) {
    if(currentNode == NULL)
        return;

    lazy(currentNode);

    print(currentNode -> left);
    fout << currentNode -> val << " ";
    print(currentNode -> right);
}

int getCnt(Node *& currentNode) {
    return (currentNode == NULL) ? 0 : currentNode -> cnt;
}

void update(Node *& currentNode) {
    if(currentNode == NULL)
        return;

    currentNode -> cnt = 1 + getCnt(currentNode -> left) + getCnt(currentNode -> right);
}

void split(Node * currentNode, Node *& tree1, Node *& tree2, int key, int add) {
    if(currentNode == NULL) {
        tree1 = tree2 = NULL;
        return;
    }

    lazy(currentNode);
    int currentKey = add + getCnt(currentNode -> left) + 1;

    if(currentKey <= key) {
        tree1 = currentNode;
        split(currentNode -> right, tree1 -> right, tree2, key, currentKey);
    }
    else {
        tree2 = currentNode;
        split(currentNode -> left, tree1, tree2 -> left, key, add);
    }
    update(currentNode);
}

void join(Node *& currentNode, Node * tree1, Node * tree2) {
    lazy(tree1);
    lazy(tree2);

    if(tree1 == NULL || tree2 == NULL) {
        currentNode = (tree1 == NULL) ? tree2 : tree1;
    }
    else if(tree1 -> priority > tree2 -> priority) {
        currentNode = tree1;
        join(currentNode -> right, tree1 -> right, tree2);
    }
    else {
        currentNode = tree2;
        join(currentNode -> left, tree1, tree2 -> left);
    }

    update(currentNode);
}

void reverse(Node*& tree, int x, int y) {
    Node * tree1 = NULL, * tree2 = NULL, * tree3 = NULL;

    split(tree, tree1, tree2, x - 1, 0);
    split(tree2, tree2, tree3, y, 0);

    tree2 -> rev ^= 1;

    join(tree, tree1, tree2);
    join(tree, tree, tree3);
}

void deleteTree(Node *& currentNode) {
    if(currentNode == NULL)
        return;

    deleteTree(currentNode -> left);
    deleteTree(currentNode -> right);
    delete currentNode;
}

void erase(Node *& tree, int x, int y) {
    Node * tree1 = NULL, * tree2 = NULL, * tree3 = NULL;

    split(tree, tree1, tree3, y, 0);
    split(tree1, tree1, tree2, x - 1, 0);

    deleteTree(tree2);
    join(tree, tree1, tree3);
}

void insert(Node *& tree, Node * newNode, int pos) {
    Node * tree1, * tree2;

    split(tree, tree1, tree2, pos - 1, 0);
    join(tree1, tree1, newNode);
    join(tree, tree1, tree2);
}

int access(Node * tree, int pos) {
    Node * tree1 = NULL, * tree2 = NULL, * tree3 = NULL;

    split(tree, tree1, tree3, pos, 0);
    split(tree1, tree1, tree2, pos - 1, 0);

    int ans = tree2 -> val;
    join(tree, tree1, tree2);
    join(tree, tree, tree3);

    return ans;
}

int getRand() {
    return 1LL * rand() * rand() % MOD;
}

int main()
{
    srand(time(NULL));

    int x, y, Q;
    char type;
    fin >> Q >> x;

    while(Q--) {
        fin >> type >> x;

        if(type == 'I') {
            fin >> y;
            Node * newNode = new Node(y, getRand());
            insert(root, newNode, x);
        }

        if(type == 'A') {
            fout << access(root, x) << '\n';
        }

        if(type == 'R') {
            fin >> y;
            reverse(root, x, y);
        }

        if(type == 'D') {
            fin >> y;
            erase(root, x, y);
        }
    }
    print(root);

    return 0;
}