Pagini recente » Cod sursa (job #1730307) | Cod sursa (job #564517) | Cod sursa (job #77166) | Cod sursa (job #587517) | Cod sursa (job #1319428)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define maxn 200010
#define maxh 1000000010
long long int v[maxn], h[maxn], poz[maxn];
int nv, nh;
void up(int n)
{
while (n/2 && v[h[n]]<v[h[n/2]])
{
swap(poz[h[n]], poz[h[n/2]]);
swap(h[n], h[n/2]);
n/=2;
}
}
void down(int n)
{
int m=2*n;
while (m<=nh)
{
m=2*n;
if (2*n<nh && v[h[2*n]]<v[h[2*n+1]]) m=2*n;
if (2*n+1<nh && v[h[2*n]]>v[h[2*n+1]]) m=2*n+1;
if (m<=nh && v[h[n]]>v[h[m]])
{
swap(poz[h[n]], poz[h[m]]);
swap(h[n], h[m]);
}
n=m;
}
}
void take(int n)
{
h[n]=h[nh];
h[nh]=maxh;
nh--;
if (n>1 && v[h[n]]<v[h[n/2]])
up(n);
else down(n);
}
int main()
{
ifstream f("heapuri.in");
ofstream g("heapuri.out");
int n, op, i, x;
f>>n;
for (i=1;i<=n;i++)
{
f>>op;
if (op==3)
g<<v[h[1]]<<'\n';
else
{
f>>x;
if (op==1)
{
nh++; nv++;
v[nv]=x;
h[nh]=nv;
poz[nv]=nh;
up(nh);
}
if (op==2)
take(poz[x]);
}
}
}