Cod sursa(job #2403618)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 11 aprilie 2019 18:56:41
Problema Heapuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
#include <fstream>

using namespace std;
ifstream cin("heapuri.in");
ofstream cout("heapuri.out");
int n,op,x,p[400050];
pair <int, int> v[400050];
void el(int ind);
void add(int a,int ind);
int main()
{
    cin>>n;
    int cnt=1;
    for(int i=1;i<=n;i++)
    {
        cin>>op;
        if(op<3)
        {
            cin>>x;
            if(op==1)
            {
                add(x,cnt++);
            }
            else el(x);
        }
        else cout<<v[1].first<<'\n';
    }
    /*
    cout<<v[0].first<<'\n';
    for(int i=1;i<=v[0].first;i++)
        cout<<v[i].first<<' ';
    cout<<'\n';
    */
    return 0;
}
void add(int a,int ind)
{
    v[++v[0].first]={a,ind};
    p[ind]=v[0].first; ///pozitia pe care se afla elementul adaugat al ind-ulea in heap este v[0].first

    int poz=v[0].first;
    while(poz/2>0 && v[poz].first < v[poz/2].first)
    {
        swap(v[poz],v[poz/2]);
        swap(p[v[poz].second], p[v[poz/2].second]);
        poz=poz/2;
    }
}
void el(int ind)
{
    int poz=p[ind],pf=0;
    swap(v[poz],v[v[0].first]);/// trebuie inetrschimbate in intregime nu doar v[pos].first
    swap(p[v[poz].second],p[v[v[0].first].second]);v[0].first--;
    if(poz/2 && v[poz/2].first>v[poz].first)
    {
        while(poz/2>0)
        {
            pf=poz/2;
            if(v[pf].first>v[poz].first)
            {
                swap(v[poz],v[pf]);
                swap(p[v[poz].second],p[v[pf].second]);
            }
            else break;
            poz=poz/2;
        }
    }
    else if(poz*2<=v[0].first){ ///este posibil ca fiul drept sa fie mai mic

        while(poz*2<=v[0].first)
        {
            pf=poz*2;
            if(poz*2+1<=v[0].first)
            {
                if(v[poz*2+1].first<v[poz*2].first)
                    pf++;
            }
            if(v[pf].first<v[poz].first)
            {
            swap(v[poz],v[pf]);
            swap(p[v[poz].second],p[v[pf].second]);
            }
            else break;
            poz=pf; /// daca te duci in fiul drept poz ia poz*2+1
        }
    }
}