Cod sursa(job #1977179)

Utilizator felixiPuscasu Felix felixi Data 5 mai 2017 08:48:43
Problema Zeap Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("zeap.in");
ofstream out("zeap.out");

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

const int INF = (1 << 30);

Arbore NIL;

struct Treap {
    int val, g, prio, mx, mn, mdif;
    Arbore left, right;
    Treap(int _val) : val(_val), g(1), prio(rand()), mx(_val), mn(_val), mdif(INF),  left(NIL), right(NIL) {}
};

void recalc( Arbore x ) {
    x->g = x->left->g + x->right->g + 1;
    x->mn = min( x->val, min(x->left->mn, x->right->mn) );
    x->mx = max( x->val, max(x->left->mx, x->right->mx) );

    x->mdif = min( x->left->mdif, x->right->mdif );
    if( x->left != NIL ) {
        x->mdif = min(x->mdif, x->val - x->left->mx);
    }
    if( x->right != NIL ) {
        x->mdif = min(x->mdif, x->right->mn - x->val);
    }
}

Arbore join(Arbore a, Arbore b) {
    if( a == NIL )
        return b;
    if( b == NIL )
        return a;

    if( a->mx > b->mn )
        swap(a, b);
    if( a->prio > b->prio ) {
        a->right = join(a->right, b);
        recalc(a);
        return a;
    }
    b->left = join(a, b->left);
    recalc(b);
    return b;

}

PAA split(Arbore x, int val) {
    if( x == NIL ) return {NIL, NIL};

    if( val == x->val ) {
        Arbore meh = x->left;
        x->left = NIL;
        recalc(x);

        return {meh, x};
    }
    if( val < x->val ) {
        PAA ans = split(x->left, val);
        x->left = NIL;
        recalc(x);

        return {ans.first, join(ans.second, x)};
    }
    PAA ans = split(x->right, val);
    x->right = NIL;
    recalc(x);

    return {join(x, ans.first), ans.second};
}

bool find_val(Arbore x, int val) {
    if( x == NIL ) return 0;
    if( x->val == val ) return 1;
    if( val < x->val ) {
        return find_val(x->left, val);
    }
    return find_val(x->right, val);
}

Arbore insert(Arbore x, int val) {
    bool este = find_val(x, val);
    if( este ) return x;

    Arbore tr = new Treap(val);
    PAA ans = split(x, val);
    return join( join(ans.first, tr), ans.second );
}

Arbore sterge(Arbore x, int val) {
    if( !find_val(x, val) ) return 0;
    if( x == NIL ) return 0;

    PAA ans = split(x, val);
    PAA sec = split(ans.second, val+1);
    return join(ans.first, sec.second);
}

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

    NIL = new Treap(0);
    NIL->g = NIL->val = 0;
    NIL->left = NIL->right = NIL;
    NIL->mn = 1000000001;
    NIL->mx = 0;
    NIL->mdif = INF;

    Arbore SMEK = NIL;

    string line;
    while( in >> line ) {
        int nr = 0;
        if( line == "MAX" ) {
            if( SMEK->g < 2 ) out << "-1\n";
            else out << SMEK->mx - SMEK->mn << '\n';
        }
        else if( line == "MIN" ) out << SMEK->mdif << '\n';
        else if( line == "C" ) {
            in >> nr;
            out << find_val( SMEK, nr ) << '\n';
        }
        else if( line == "I" ) {
            in >> nr;
            SMEK = insert(SMEK, nr);
        }
        else if( line == "S" ){
            in >> nr;
            if( !find_val(SMEK, nr) ) out << "-1\n";
            else SMEK = sterge(SMEK, nr);
        }
    }
    return 0;
}