Cod sursa(job #2480217)

Utilizator Coroian_DavidCoroian David Coroian_David Data 25 octombrie 2019 08:11:26
Problema Secv8 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <bits/stdc++.h>

using namespace std;

const int MOD = (1 << 30) - 1;

struct nod
{
    int nr;
    int pr;
    int dim;
    int flip;
    nod *st, *dr;

    nod(int _nr, int _pr, int _dim, int _flip) : nr(_nr), pr(_pr), dim(_dim), flip(_flip) {};
};

nod *nil = new nod{0, 0, 0, 0};

void upd(nod *n)
{
   // if(n == NULL)
   //     cout <<"EROARE\n";

   // cout << n << "\n";

    if(n == nil)
        return;

    if(n -> flip == 1)
    {
        if(n -> st != nil)
            n -> st -> flip ^= 1;
        if(n -> dr != nil)
            n -> dr -> flip ^= 1;
        swap(n -> st, n -> dr);

        n -> flip = 0;
    }
}

nod* mfiu(nod *n, int care, nod *fiu)
{
    //cout << n << " " << fiu << "\n";

    upd(n);

    (care == 0 ? n -> st : n -> dr) = fiu;
    n -> dim = n -> st -> dim + n -> dr -> dim + 1;
}

nod* join(nod *a, nod *b)
{
    //cout << a << " " << b << "\n";

    upd(a);
    upd(b);

    if(a == nil)
        return b;

    if(b == nil)
        return a;

    if(a -> pr > b -> pr)
        return mfiu(a, 1, join(a -> dr, b));

    else
        return mfiu(b, 0, join(a, b -> st));
}

pair <nod*, nod*> split(nod *n, int k)
{
    //cout << n << "\n";

    if(n == nil)
        return {nil, nil};

    upd(n);

    if(n -> st -> dim + 1 <= k)
    {
        auto tmp = split(n -> dr, k - n -> st -> dim - 1);
        return {mfiu(n, 1, tmp.first), tmp.second};
    }

    auto tmp = split(n -> st, k);
    return {tmp.first, mfiu(n, 0, tmp.second)};
}

ofstream g("secv8.out");

void doAfis(nod *n)
{
    //cout << n << "\n";

    if(n == nil)
        return;

    upd(n);

    doAfis(n -> st);
    g << n -> nr << " ";
    doAfis(n -> dr);
}

void ansQues()
{
    ifstream f("secv8.in");

    nod *rad = nil;

    int q, x;
    f >> q >> x;
    while(q > 0)
    {
        q --;

        int k, e;
        char tip;
        f >> tip;
        if(tip == 'I')
        {
            f >> k >> e;
            auto tmp = split(rad, k - 1);
            nod *nou = new nod{e, (int)((1LL * rand() * rand()) & MOD), 1, 0};
            nou -> st = nou -> dr = nil;
            //cout << tmp.first << " " << tmp.second << "\n";
            rad = join(tmp.first, join(nou, tmp.second));
        }

        else
            if(tip == 'A')
            {
                f >> k;
                auto tmp = split(rad, k - 1);
                auto tmp2 = split(tmp.second, 1);
                g << tmp2.first -> nr << "\n";

                //cout << tmp.first << " " << tmp2.first << " " << tmp2.second << "\n";

                rad = join(tmp.first, join(tmp2.first, tmp2.second));
            }

        else
        {
            int i, j;
            f >> i >> j;
            auto tmp = split(rad, j);
            auto tmp2 = split(tmp.first, i - 1);

            if(tip == 'D')
            {
                delete tmp2.second;
                tmp2.second = nil;
            }

            if(tip == 'R')
                tmp2.second -> flip ^= 1;

            //cout << tmp.first << " " << tmp2.first << " " << tmp2.second << "\n";

            rad = join(join(tmp2.first, tmp2.second), tmp.second);
        }


        //doAfis(rad);
        //g << "++\n";
    }

    doAfis(rad);
    g << "\n";

    f.close();
    g.close();
}

int main()
{
    ansQues();

    return 0;
}