Cod sursa(job #2505495)

Utilizator ArdeleanOficialayy lmao ArdeleanOficial Data 6 decembrie 2019 22:31:39
Problema Secv8 Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.45 kb
#include <bits/stdc++.h>

using namespace std;

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

mt19937 rnd((long long)(new char));

typedef struct Treap * Arbore;
typedef pair < Arbore, Arbore > Paa;

Arbore NIL;

struct Treap {
    bool flip;
    int val;
    int nl;
    long long prio;
    Arbore st, dr;

    void propaga() {
        if (!flip)
            return;
        swap(st, dr);
        st->flip ^= 1;
        dr->flip ^= 1;
        flip = 0;
    }

    void recalc() {
        nl = 1 + st->nl + dr->nl;
    }

    Paa Split(int poz) {///ma pierd
        assert(poz <= nl);
        if (this == NIL)
            return {NIL, NIL};
        propaga();
        if (st->nl < poz) {
            Paa ans(dr->Split(poz - st->nl - 1));
            dr = ans.first;
            recalc();
            return {this, ans.second};
        }
        else {///eu sunt in second
            Paa ans(st->Split(poz));
            st = ans.second;
            recalc();
            return {ans.first, this};
        }
    }

    Arbore Insert(int poz, int val);
    Arbore Delete(int l, int r);
    Arbore Reverse(int l, int r);
    int Access(int l);
    void Dfs() {
        if (this == NIL)
            return;
        st->Dfs();
        fout << val << ' ';
        dr->Dfs();
    }

    Treap(int val = 0) : flip(0), val(val), nl(1), prio(rnd()), st(NIL),  dr(NIL) { }
};

Arbore Join(Arbore x, Arbore y) {///se pierd x si y
    if (x == NIL)
        return y;
    if (y == NIL)
        return x;
    if (x->prio < y->prio) {///y sus
        y->propaga();
        Arbore ans = Join(x, y->st);
        y->st = ans;
        y->recalc();
        return y;
    }
    else {
        x->propaga();
        Arbore ans = Join(x->dr, y);
        x->dr = ans;
        x->recalc();
        return x;
    }
}

Arbore Treap::Insert(int poz, int val) {
    propaga();
    Paa ans = Split(poz - 1);
    Arbore eu = new Treap(val);
    ans.first = Join(ans.first, eu);
    return Join(ans.first, ans.second);
}

Arbore Treap::Delete(int l, int r) {
    propaga();
    Paa ans = Split(r);
    Paa aux = ans.first->Split(l - 1);
    return Join(aux.first, ans.second);
}

Arbore Treap::Reverse(int l, int r) {
    propaga();
    Paa ans = Split(r);
    Paa aux = ans.first->Split(l - 1);
    aux.second->flip ^= 1;
    aux.second->propaga();
    ans.first = Join(aux.first, aux.second);
    return Join(ans.first, ans.second);
}

int Treap::Access(int poz) {
    propaga();
    assert(this != NIL);
    if (poz == st->nl + 1)
        return val;
    if (poz <= st->nl)
        return st->Access(poz);
    return dr->Access(poz - st->nl - 1);
}

int main()
{
    NIL = new Treap;
    NIL->nl = 0;
    NIL->st = NIL->dr = NIL;
    NIL->prio = 0;

    Arbore Eu = NIL;

    int q, a, b, TALENTUMAPARASITDEMULTEMOMENTULSAMALAS;
    fin >> q >> TALENTUMAPARASITDEMULTEMOMENTULSAMALAS;
    char type;
    while (q--) {
        fin >> type;
        if (type == 'I') {
            fin >> a >> b;
            Eu = Eu->Insert(a, b);
        }
        else if (type == 'A') {
            fin >> a;
            fout << Eu->Access(a) << '\n';
        }
        else if (type == 'D') {
            fin >> a >> b;
            Eu = Eu->Delete(a, b);
        }
        else {///if (type == 'R')
            fin >> a >> b;
            Eu = Eu->Reverse(a, b);
        }
    }
    Eu->Dfs();
    return 0;
}