Cod sursa(job #1756667)

Utilizator CrystyAngelDinu Cristian CrystyAngel Data 13 septembrie 2016 13:10:23
Problema Heapuri Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("heapuri.in");
ofstream fout("heapuri.out");

#define nmax 200100

int n,m,o,p,x;
int h[nmax];
int v[nmax];
int t[nmax];

void up(int p)
{
    while(p>1 && h[p]<h[p/2])
    {
        swap(h[p],h[p/2]);
        swap(v[t[p]],v[t[p/2]]);
        swap(t[p],t[p/2]);
        p/=2;
    }
}

void down(int p)
{
    if((p<<1)<=n && (p<<1)+1<=n && v[p<<1]<v[(p<<1)+1] && v[p<<1]<v[p])
    {
        swap(h[p],h[p<<1]);
        swap(v[t[p]],v[t[p<<1]]);
        swap(t[p],t[p<<1]);
        down(p<<1);
    }
    else
    if((p<<1)<=n && (p<<1)+1<=n && v[p<<1]>v[(p<<1)+1] && v[(p<<1)+1]<v[p])
    {
        swap(h[p],h[p<<1]);
        swap(v[t[p]],v[t[p<<1]]);
        swap(t[p],t[p<<1]);
        down((p<<1)+1);
    }
    else
    if((p<<1)<=n && v[p<<1]<v[p])
    {
        swap(h[p],h[p<<1]);
        swap(v[t[p]],v[t[p<<1]]);
        swap(t[p],t[p<<1]);
        down(p<<1);
    }
}

int main()
{
    fin>>m;
    for( ; m; --m)
    {
        fin>>p;
        switch(p)
        {
        case 1:
            fin>>x;
            h[++n]=x;
            v[++o]=n;
            t[n]=o;
            up(n);
            break;
        case 2:
            fin>>x;
            p=v[x];
            swap(h[p],h[n]);
            swap(v[t[p]],v[t[n]]);
            swap(t[p],t[n]);
            --n;
            up(p);
            down(p);
            break;
        case 3:
            fout<<h[1]<<'\n';
            break;
        }
    }
}