Pagini recente » Monitorul de evaluare | Borderou de evaluare (job #1567219) | Cod sursa (job #2078084)
#include<cstdio>
#include<algorithm>
using namespace std;
const int nmax=600000,vid=1000000001;
int valhp[nmax+5],lh;//valoarea la cheia hp
int cheihp[nmax+5],ch;//pe ce poz e al n-lea
int nrhp[nmax+5],nh;//al catelea e el. de la cheia n
void schimba(int p1,int p2)
{
swap(nrhp[p1],nrhp[p2]);
swap(cheihp[nrhp[p1]],cheihp[nrhp[p2]]);
swap(valhp[p1],valhp[p2]);
}
void goup(int poz)
{
while(valhp[poz]<valhp[poz/2] && poz>1)
{
schimba(poz,poz/2);
poz=poz/2;
}
}
void godown(int poz)
{
if(valhp[poz*2]==vid && valhp[poz*2+1]==vid)
return ;
if(valhp[poz*2]==vid || valhp[poz*2+1]<valhp[poz*2])
{
schimba(poz,poz*2+1);
if(valhp[poz*2]!=vid)
godown(poz*2+1);
}
else
if(valhp[poz*2+1]==vid || valhp[poz*2]<valhp[poz*2+1])
{
schimba(poz,poz*2);
if(valhp[poz*2+1]!=vid)
godown(poz*2);
}
return ;
}
void insertv(int e,int nre)
{
lh++;
valhp[lh]=e;
cheihp[nre]=lh;
nrhp[lh]=nre;
goup(lh);
}
void deletev(int poz)
{
valhp[poz]=vid;
godown(poz);
}
int main()
{
freopen("heapuri.in","r",stdin);
freopen("heapuri.out","w",stdout);
int t,q,n,i,j,tip,e,nre=0;
lh=0;
for(i=1;i<=nmax;i++)
valhp[i]=cheihp[i]=vid;
scanf("%d",&t);
for(q=1;q<=t;q++)
{
scanf("%d",&tip);
if(tip!=3)
scanf("%d",&e);
if(tip==1)
{
nre++;
insertv(e,nre);
}
if(tip==2)
{
// printf("**%d\n",valhp[cheihp[e]]);
deletev(cheihp[e]);
}
if(tip==3)
{
printf("%d\n",valhp[1]);
}
}
return 0;
}