Pagini recente » Cod sursa (job #2056592) | Borderou de evaluare (job #829065) | Cod sursa (job #1873828)
#include <bits/stdc++.h>
#define nmax 200001
using namespace std;
ifstream f("heapuri.in");
ofstream g("heapuri.out");
int n,m;
int poz[nmax];
struct heap
{int val,p;};
heap H[nmax];
void InsertVal(int x)
{int fiu,tata;
fiu=++n;
tata=n/2;
while(tata&&H[tata].val>x)
{H[fiu]=H[tata];
poz[H[tata].p]=fiu;
fiu=tata;
tata=fiu/2;
}
H[fiu].val=x;
H[fiu].p=m;
poz[x]=fiu;
}
void comb(int i)
{int v=H[i].val,tata=i,fiu=2*i;
while(fiu<=n)
{if(fiu<n)
if(H[fiu].val>H[fiu+1].val) fiu++;
if(v>H[fiu].val)
{H[tata]=H[fiu];
poz[H[fiu].p]=tata;
tata=fiu; fiu=fiu*2;
}
else
fiu=n+1;
}
H[tata].val=v;
poz[v]=tata;
}
void elim(int k)
{H[k]=H[n];
poz[H[n].p]=k;
--n;
comb(k);
}
void read()
{int i,cod,x,nr;
f>>nr;
for(i=1;i<=nr;i++)
{f>>cod;
if(cod==1)
{ f>>x; ++m;
InsertVal(x);
}
if(cod==2)
{f>>x;
elim(poz[x]);
}
if(cod==3) g<<H[1].val<<"\n";
/*
for(int j=1;j<=n;j++)
g<<H[j].val<<" ";
g<<"\n";
*/
}
}
int main()
{read();
return 0;
}