Cod sursa(job #2615992)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 16 mai 2020 13:51:25
Problema Zeap Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.17 kb
#include <bits/stdc++.h>
#define INF 2e9
#define MODULO 666013

using namespace std;

class Treap
{
public:
    struct nodTreap
    {
        nodTreap *st;
        nodTreap *dr;
        int minim;
        int maxim;
        int minDif;
        int valoare;
        int prioritate;
        nodTreap(nodTreap *leftson, nodTreap *rightson, int valoare1, int minim1, int maxim1, int minDif1, int prioritate1)
        {
            this->st = leftson;
            this->dr = rightson;
            valoare = valoare1;
            minim = minim1;
            maxim = maxim1;
            minDif = minDif1;
            prioritate = prioritate1;
        }
    };

    nodTreap *root, *NILL;

    Treap()
    {
        srand(time(NULL));
        NILL = new nodTreap(NULL, NULL, 0, 0, 0, 0, 0);
        root = NILL;
    }

    int MinDif()
    {
        if(root->minDif && root->minDif != INF)
            return root->minDif;

        return -1;
    }

    int MaxDif()
    {
        if(root->maxim != root->minim && root->maxim - root->minim != INF)
            return root->maxim - root->minim;

        return -1;
    }

    void Recheck(nodTreap *&node)
    {
        if(node == NILL)
            return;

        node->minim = node->valoare;
        node->maxim = node->valoare;
        node->minDif = INF;

        if(node->st != NILL)
        {
            node->minim = min(node->minim, node->st->minim);
            node->maxim = max(node->maxim, node->st->maxim);
            node->minDif = min(node->minDif, node->valoare - node->st->maxim);
            node->minDif = min(node->minDif, node->st->minDif);
        }
        if(node->dr != NILL)
        {
            node->minim = min(node->minim, node->dr->minim);
            node->maxim = max(node->maxim, node->dr->maxim);
            node->minDif = min(node->minDif, node->dr->minim - node->valoare);
            node->minDif = min(node->minDif, node->dr->minDif);
        }
    }

    void LeftRotate(nodTreap *&node)
    {
        nodTreap *aux = node->dr;
        node->dr = aux->st;
        aux->st = node;
        node = aux;

        Recheck(node->st);
        Recheck(node->dr);
        Recheck(node);
    }

    void RightRotate(nodTreap *&node)
    {
        nodTreap *aux = node->st;
        node->st = aux->dr;
        aux->dr = node;
        node = aux;

        Recheck(node->st);
        Recheck(node->dr);
        Recheck(node);
    }

    void Balance(nodTreap *&node)
    {
        if(node->st != NILL && node->st->prioritate > node->prioritate)
            RightRotate(node);
        if(node->dr != NILL && node->dr->prioritate > node->prioritate)
            LeftRotate(node);

        Recheck(node);
    }

    void Insert(nodTreap *&node, int val)
    {
        if(node == NILL)
        {
            node = new nodTreap(NILL, NILL, val, val, val, INF, rand() % MODULO + 1);
            return;
        }
        else if(node->valoare > val)
            Insert(node->st, val);
        else if(node->valoare < val)
            Insert(node->dr, val);

        Balance(node);
    }

    int Search(nodTreap *&node, int val)
    {
        if(node == NILL)
            return 0;
        if(node->valoare > val)
            return Search(node->st, val);
        else if(node->valoare < val)
            return Search(node->dr, val);

        return 1;
    }

    void Remove(nodTreap *&node, int val)
    {
        if(node->valoare > val)
            Remove(node->st, val);
        else if(node->valoare < val)
            Remove(node->dr, val);
        else
        {
            if(node->st == NILL && node->dr == NILL)
            {
                delete node;

                node = NILL;
                return;
            }
            else if(node->st != NILL && node->dr != NILL)
            {
                if(node->st->prioritate > node->dr->prioritate)
                    RightRotate(node);
                else
                    LeftRotate(node);

                Remove(node, val);
            }
            else
            {
                if(node->st != NILL)
                    RightRotate(node);
                else
                    LeftRotate(node);

                Remove(node, val);
            }
        }

        Balance(node);
    }
};

int main()
{
    ifstream fin("zeap.in");
    ofstream fout("zeap.out");

    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);

    Treap *t = new Treap();
    string c;
    int v;

    int cnt = 0;
    while(fin >> c)
    {
        cnt++;

        if(c == "I")
        {
            fin >> v;
            t->Insert(t->root, v);
        }
        else if(c == "C")
        {
            fin >> v;
            fout << t->Search(t->root, v) << '\n';
        }
        else if(c == "S")
        {
            fin >> v;
            if(t->Search(t->root, v) == 0)fout << -1 << '\n';
            else t->Remove(t->root, v);
        }
        else if(c == "MAX")
            fout << t->MaxDif() << '\n';
        else
            fout << t->MinDif() << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}