Cod sursa(job #1943825)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 28 martie 2017 20:38:41
Problema Zeap Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

set<int> heap;
multiset<int> mdif;
char line[100000];

inline int abs(int x)
{
    if(x >= 0)
        return x;
    return -1 * x;
}

int main()
{
    freopen("zeap.in","r",stdin);
    freopen("zeap.out","w",stdout);

    while(fgets(line,100000,stdin))
    {
        char *p = strtok(line," \n");
        if(!strcmp(p,"I"))
        {
            int param;
            p = strtok(NULL," \n");
            sscanf(p,"%d",&param);

            if(heap.find(param) != heap.end())
                continue;
            if(!heap.size())
            {
                heap.insert(param);
                continue;
            }
            auto it = heap.upper_bound(param), it2 = it;
            if(it != heap.begin())
            {
                it2 = it; it2--;
                if(*it > param)
                {
                    auto it3 = mdif.find(*it - *it2);
                    if(it3 != mdif.end())
                    {
                        mdif.erase(it3);
                    }
                    if (*it - param < param - *it2)
                        mdif.insert(*it - param);
                    else
                        mdif.insert(param - *it2);
                }
                else mdif.insert(param - *it2);

            }
            else
            {
                if (*it > param)
                    mdif.insert(*it - param);
            }
            heap.insert(param);
        }
        else if(!strcmp(p,"S"))
        {
            int param;
            p = strtok(NULL," \n");
            sscanf(p,"%d",&param);

            if (heap.find(param) == heap.end())
            {
                printf("-1\n");
                continue;
            }

            auto it = heap.lower_bound(param), it2 = heap.upper_bound(param), it3 = it;
            if(it != heap.begin())
            {
                it3--;
                auto k = mdif.find(param - *it3);
                if(k != mdif.end())
                {
                    mdif.erase(k);
                }
                if(it2 != heap.end())
                {
                    k = mdif.find( *it2 - param);
                    if (k != mdif.end())
                        mdif.erase(k);
                    mdif.insert( *it2 - *it3 );
                }
            }
            else
            {
                if(it2 != heap.end())
                {
                    auto k = mdif.find(*it2 - param);
                    if (k != mdif.end())
                        mdif.erase(k);
                }
                heap.erase(heap.lower_bound(param));
            }
        }
        else if(!strcmp(p,"C"))
        {
            int param;
            p = strtok(NULL," \n");
            sscanf(p,"%d",&param);
            printf("%d\n",heap.find(param)!=heap.end());
        }
        else if(!strcmp(p,"MAX"))
        {
            printf("%d\n",*(heap.rbegin())-*(heap.begin()));
        }
        else if(!strcmp(p,"MIN"))
        {
            printf("%d\n",*mdif.begin());

        }
    }
    return 0;
}