Cod sursa(job #1963948)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 12 aprilie 2017 22:21:12
Problema Zeap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb
#include <bits/stdc++.h>
#define mid ((st+dr)/2)

using namespace std;

const int inf = 1e9 + 1;

ifstream fin("zeap.in"); ofstream fout("zeap.out");
string type;
int x;

class Node
{
    Node *left, *right;
    int min_dif, max_val, min_val;

    void refresh()
    {
        if(left && right)
        {
            max_val = max(left -> max_val, right -> max_val);
            min_val = min(left -> min_val, right -> min_val);

            min_dif = min(left -> min_dif, right -> min_dif);
            min_dif = min(min_dif, right -> min_val - left -> max_val);
            return;
        }

        if(!left) max_val = right -> max_val, min_val = right -> min_val, min_dif = right -> min_dif;
            else max_val = left -> max_val, min_val = left -> min_val, min_dif = left -> min_dif;
    }

    public:

        Node()
        {
            left = right = NULL;
            max_val = 0; min_dif = min_val = inf;
        }

        void add(int st, int dr, int val)
        {
            if(st==dr)
            {
                max_val = min_val = val;
                return;
            }

            if(val<=mid)
            {
                if(!left) left = new Node;
                left -> add(st, mid, val);
            }
            else
            {
                if(!right) right = new Node;
                right -> add(mid+1, dr, val);
            }

            refresh();
        }

        bool cauta(int st, int dr, int val)
        {
            if(st==dr) return max_val;

            if(val<=mid)
            {
                if(!left) return 0;
                return left -> cauta(st, mid, val);
            }
            else
            {
                if(!right) return 0;
                return right -> cauta(mid+1, dr, val);
            }
        }

        bool sterge(int st, int dr, int val)
        {
            if(st==dr)
            {
                if(!max_val) return 0;
                max_val = 0;
                min_val = inf;
                return 1;
            }

            bool ok;

            if(val<=mid)
            {
                if(!left) return 0;
                ok = left -> sterge(st, mid, val);
            }
            else
            {
                if(!right) return 0;
                ok = right -> sterge(mid+1, dr, val);
            }

            refresh();
            return ok;
        }

        int query_max_dif()
        {
            if(max_val <= min_val) return -1;
            return max_val - min_val;
        }

        int query_min_dif()
        {
            if(max_val <= min_val) return -1;
            return min_dif;
        }


} *root = new Node;

int main()
{
    while(fin >> type)
    {
        if(type == "MAX") fout << root -> query_max_dif() << '\n';
            else if(type == "MIN") fout << root -> query_min_dif() << '\n';

        if(type.size() == 3) continue;

        fin >> x;
        if(type == "I") root -> add(1, inf, x);
            else if(type == "C") fout << (root -> cauta(1, inf, x)) << '\n';
                else if(!root -> sterge(1, inf, x)) fout << -1 << '\n';
    }

    return 0;
}