Pagini recente » Borderou de evaluare (job #2288295) | Cod sursa (job #2288296)
#include<fstream>
using namespace std;
ifstream cin("heapuri.in");
ofstream cout("heapuri.out");
int q,c,x,n,m,v[200005],h[200005],p[200005];
void downheap(int k){
int nod;
do{
nod=0;
if(2*k<=n){
nod=2*k;
if(2*k+1<=n && v[h[2*k+1]]<v[h[2*k]])
nod=2*k+1;
if(v[h[k]]<v[h[nod]])
nod=0;
}
if(nod){
swap(h[k],h[nod]);
swap(p[h[k]],p[h[nod]]);
k=nod;
}
}while(nod);
}
void upheap(int k){
int key=h[k];
while(k>1 && v[h[k/2]]>v[key]){
h[k]=h[k/2];
p[h[k]]=k;
k=k/2;
}
h[k]=key; p[h[k]]=k;
}
void eliminate(int k){
h[k]=h[n]; p[h[k]]=k; --n;
if(k>1 && v[h[k/2]]>v[h[k]])
upheap(k);
else downheap(k);
}
int main(){
cin>>q;
while(q--){
cin>>c;
if(c==3) cout<<v[h[1]]<<'\n';
else{
cin>>x;
if(c==1){
v[++m]=x;
h[++n]=m;
p[m]=n;
upheap(n);
}
else eliminate(p[x]);
}
}
}