Cod sursa(job #1951675)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 3 aprilie 2017 19:05:02
Problema Zeap Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.49 kb
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstdio>
using namespace std;

const int INF = 0x3f3f3f3f;
int n;

struct Treap
{
    int key, priority;

    int minim, maxim, mindif;

    Treap *left, *right;

    Treap(){}

    Treap(int key,int priority,Treap *left, Treap *right)
    {
        this->key = key, this->priority = priority, this->left = left, this->right = right;
        maxim = -INF, minim= INF, mindif =INF;
    }
}*root,*nil;

void solve();

int main()
{
    srand(time(0));
    solve();
    return 0;
}

void left_rot(Treap *&node)
{
    Treap *aux = node->left;
    node->left = aux->right;
    aux->right = node;
    node = aux;
}

void right_rot(Treap *&node)
{
    Treap *aux = node->right;
    node->right = aux->left;
    aux->left = node;
    node = aux;
}

void update(Treap* &node)
{
    if(node == nil)
        return;

    node->minim = min(node->key, node->left->minim);
    node->maxim = max(node->key, node->right->maxim);
    node->mindif = min(min(node->left->mindif, node->right->mindif),\
                        min(node->key - node->left->maxim, node->right->minim - node->key));
}

void balance(Treap *&node)
{
    if(node->left->priority > node->priority)
    {
        left_rot(node);
        update(node->right);
    }
    else if(node->right->priority > node->priority)
    {
        right_rot(node);
        update(node->left);
    }
    update(node);
}

void ins(Treap *&node, int key)
{
    if(node == nil)
    {
        node = new Treap(key,rand()+1,nil,nil);
        node->maxim = node->minim = key;
        n++;
        return;
    }
    if(key < node->key)
        ins(node->left,key);
    else ins(node->right, key);

    balance(node);
    update(node);
}

bool src(Treap *node,int key)
{
    if(node == nil)
        return 0;
    if(node->key == key)
        return 1;
    if(key < node->key)
        return src(node->left,key);
    return src(node->right, key);
}

void rm(Treap* &node,int key)
{
    if(node == nil)
        return;
    if(key < node->key)
        rm(node->left, key);

    else if( key > node->key)
        rm(node->right, key);

    else
    {
        if(node->left == nil && node->right == nil)
        {
            --n;
            delete node;
            node = nil;
            return;
        }
        else
        {
            if(node->left->priority > node->right->priority)
                left_rot(node);
            else
                right_rot(node);
            rm(node,key);
        }
    }
    update(node);
}

char s[20];

void solve()
{
    root = nil = new Treap(0,0,0,0);
    freopen("zeap.in","r",stdin);
    freopen("zeap.out","w",stdout);

    while(gets(s))
    {
        if(*s == 'I')
        {
            int key;
            sscanf(s+2,"%d",&key);
            ins(root,key);
        }
        else if(*s == 'S')
        {
            int key;
            sscanf(s+2,"%d",&key);
            if(!src(root,key))
                printf("-1\n");
            else rm(root,key);
        }
        else if(*s == 'C')
        {
            int key;
            sscanf(s+2,"%d",&key);
            printf("%d\n",src(root,key));
        }
        else if(*s == 'M')
        {
            if(n<2)
            {
                printf("-1\n");
            }
            else
            {
                if(s[1] == 'A')
                {
                    printf("%d\n",root->maxim - root->minim);
                }
                else
                {
                    printf("%d\n",root->mindif);
                }
            }
        }
    }
}