Cod sursa(job #883676)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 20 februarie 2013 11:34:16
Problema Heapuri Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
using namespace std;
int h[200001];
int poz[200001];
int val[200001];
void insheap(int fiu, int n)
{
    int v=h[fiu],tata;
    tata=fiu/2;
    while((val[v]<val[h[tata]])&&(tata>0))
    {
        h[fiu]=h[tata];
        poz[h[tata]]=fiu;
        fiu=tata;
        tata=fiu/2;
    }
    h[fiu]=v;
    poz[v]=fiu;
    tata=fiu;
    fiu=2*tata;
    while((val[v]>val[h[fiu]])&&(fiu<=n))
    {
        if(fiu<n)
            if(val[h[fiu+1]]<val[h[fiu]]) fiu++;
        h[tata]=h[fiu];
        poz[h[fiu]]=tata;
        tata=fiu;
        fiu=tata*2;
    }
    h[tata]=v;
    poz[v]=tata;
}
int main()
{
    int n,x,nh=0,i,op,np=0;
    ifstream f("heapuri.in");
    f>>n;
    ofstream g("heapuri.out");
    for(i=1;i<=n;i++)
    {
        f>>op;
        switch(op)
        {
            case 1:
            {
                f>>x;
                nh++;np++;
                val[np]=x;
                h[nh]=np;
                poz[np]=nh;
                if(nh>1)
                    insheap(nh,nh);
                break;
            }
            case 2:
            {
                f>>x;
                h[poz[x]]=h[nh];
                poz[h[nh]]=poz[x];
                nh--;
                insheap(poz[x],nh);
                break;

            }
            case 3:
            {
                g<<val[h[1]]<<"\n";
                break;
            }
        }
    }
    f.close();
    g.close();
    return 0;
}