Cod sursa(job #1950025)

Utilizator LucianTLucian Trepteanu LucianT Data 2 aprilie 2017 17:07:12
Problema Zeap Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.37 kb
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
struct treap
{
    int key;
    int priority;
    int maxx;
    int minn;
    int difmin;

    treap *st,*dr;
    treap(int key,int priority,treap *st,treap *dr,int minn,int maxx,int difmin)
    {
        this->key=key;
        this->priority=priority;
        this->st=st;
        this->dr=dr;
        this->minn=minn;
        this->maxx=maxx;
        this->difmin=difmin;
    }
}*root,*nil;
int cntnodes,removed;

void _update(treap *nod)
{
    nod->minn=min(nod->key, min(nod->st->minn,nod->dr->minn));
    nod->maxx=max(nod->key, max(nod->st->maxx,nod->dr->maxx));
    nod->difmin=min(abs(nod->key - nod->st->maxx), min(abs(nod->dr->minn - nod->key),min(nod->st->difmin, nod->dr->difmin)));
}

void rotleft(treap *&nod)
{
    treap *aux=nod->st;
    nod->st=aux->dr;
    aux->dr=nod;
    nod=aux;

    if(nod!=nil && nod->dr!=nil)
        _update(nod->dr);
    //_update(nod);
}
void rotright(treap *&nod)
{
    treap *aux=nod->dr;
    nod->dr=aux->st;
    aux->st=nod;
    nod=aux;

    if(nod!=nil && nod->st!=nil)
        _update(nod->st);
    //_update(nod);
}
void balance(treap *&nod)
{
    if(nod->st && nod->priority<nod->st->priority)
        rotleft(nod);
    else if(nod->dr && nod->priority<nod->dr->priority)
        rotright(nod);
    _update(nod);
}
void _insert(treap *&nod,int cheie,int prior)
{
    if(nod==nil){
        nod=new treap(cheie,prior,nil,nil,cheie,cheie,INF);
        cntnodes++;
        return;

    }
    if(cheie<nod->key)
        _insert(nod->st,cheie,prior);
    else if(cheie>nod->key)
        _insert(nod->dr,cheie,prior);

    balance(nod);
}
void _erase(treap *&nod,int val)
{
    if(nod==nil)
        return;
    if(nod->key>val)
        _erase(nod->st,val);
    else if(nod->key<val)
        _erase(nod->dr,val);

    else
    {
        if(nod->st==nil && nod->dr==nil){
            delete nod;
            cntnodes--;
            nod=nil;
            removed=1;
        }
        else
        {
            if(nod->st->priority>nod->dr->priority)
                rotleft(nod);
            else rotright(nod);
            _erase(nod,val);
        }
    }

    if(nod!=nil)
        _update(nod);
}
int _search(treap *nod,int val)
{
    if(nod==nil)
        return 0;
    if(nod->key==val)
        return 1;

    if(val<nod->key)
        return _search(nod->st,val);
    else return _search(nod->dr,val);
}
char str[30];
int main()
{
    srand(time(0));

    ifstream f("zeap.in");
    ofstream g("zeap.out");
    root=nil=new treap(0,0,NULL,NULL,INF,-INF,INF);
    int x;

    while(f>>str)
    {
        if(str[0]=='I'){
            f>>x;
            _insert(root,x,rand()%INF+1);
            continue;
        }
        if(str[0]=='S'){
            f>>x;
            if(!_search(root,x))
                g<<-1<<'\n';
            _erase(root,x);
            continue;
        }
        if(str[0]=='C'){
            f>>x;
            g<<_search(root,x)<<'\n';
            continue;
        }
        if(str[1]=='I'){
            if(cntnodes>=2)
                g<<root->difmin<<'\n';
            else g<<-1<<'\n';
        }
        else{
            if(cntnodes>=2)
                g<<root->maxx-root->minn<<'\n';
            else g<<-1<<'\n';
        }
    }
    return 0;
}