Cod sursa(job #1255312)

Utilizator DjokValeriu Motroi Djok Data 4 noiembrie 2014 17:56:46
Problema Heapuri Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("heapuri.in");
ofstream cout("heapuri.out");
const int MAX=200005;
 
int t, o, i, h[MAX], n, k, a[MAX], index[MAX], x;
 
void upheap() {
    while (k>1 && a[h[k]]<a[h[k/2]])
    {
        swap(index[h[k]], index[h[k/2]]);
        swap(h[k], h[k/2]);
        k/=2;
    }
}
 
void downheap()
{
    int nod=1;
    do
    {
        nod=0;
        if (k*2<=i) {
                      nod=k*2;
                      if (k*2+1<=i && a[h[2*k+1]]<a[h[2*k]]) nod=k*2+1;
                      if (a[h[nod]]>=a[h[k]]) nod=0;
                    }
 
    if (nod)
    {
        swap(index[h[k]], index[h[nod]]);
        swap(h[k], h[nod]);
        k=nod;
    }
} while (nod);
}
 
 
void cut() {
    index[h[i]]=k; swap(h[k],h[i--]);
 
    if ((k > 1) && (a[h[k]] < a[h[k/2]])) {
        upheap();
    } else {
        downheap();
    }
}
 
 
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>o;
        if (o==3) cout<<a[h[1]]<<'\n';
        if (o==1)
        {
            cin>>x;
            a[++n]=x;
            h[++i]=n;
            index[n]=i;
            k=i;
            upheap();
        }
        if (o==2)
        {
            cin>>x; k=index[x];
            cut();
        }
    }
 return 0;
}