Cod sursa(job #1943864)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 28 martie 2017 20:55:53
Problema Zeap Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.45 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
#define fastcall __attribute__((optimize("-O3")))
#define inline __inline__ __attribute__((always_inline))

using namespace std;

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

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

inline fastcall void parse(int &x,char *p)
{
    x = 0;
    for(int i=0;p[i]>='0' && p[i]<='9';i++)
    {
        x = x * 10 + p[i] - '0';
    }
}

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

    while(fgets(line,120,stdin))
    {
        char *p = strtok(line," \n");
        if(!strcmp(p,"I"))
        {
            int param;
            p = strtok(NULL," \n");
            parse(param,p);

            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 k= mdif.find(*it - *it2);
                    if(k != mdif.end())
                    {
                        mdif.erase(k);
                    }
                    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");
            parse(param,p);

            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 = it;
                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");
            parse(param,p);
            printf("%d\n",heap.find(param)!=heap.end());
        }
        else if(!strcmp(p,"MAX"))
        {
            if(heap.size()<2)
                printf("-1\n");
            else printf("%d\n",*heap.rbegin()-*heap.begin());
        }
        else if(!strcmp(p,"MIN"))
        {
            if(heap.size()<2)
                printf("-1\n");
            printf("%d\n",*mdif.begin());
        }
    }
    return 0;
}