Pagini recente » Cod sursa (job #1710223) | Cod sursa (job #748879) | Cod sursa (job #1276490) | Profil butasebi | Cod sursa (job #1225530)
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
/// Heap
using namespace std;
int t, n, m, op, x, ax;
int hp[200005], b[200005], a[200005];
void UP(int p)
{
if(p/2<1) return ;
if(hp[p]<hp[p/2])
{
swap(hp[p], hp[p/2]);
a[m]=p/2;
a[b[p/2]]=p;
b[p]=b[p/2];
b[p/2]=m;
UP(p/2);
}
}
void DOWN(int p)
{
if(p*2>n) return ;
if(hp[p]>hp[p*2]&&hp[p]>hp[p*2+1])
{
if(hp[p*2]<hp[p*2+1])
{
swap(hp[p], hp[p*2]);
// int ap2=a[b[p*2]];
// int ap=a[b[p]];
int bp=b[p];
// int bp2=b[p*2];
a[b[p*2]]=p;
b[p]=b[p*2];
a[bp]=p*2;
b[p*2]=bp;
DOWN(p*2);
}
else
{
swap(hp[p], hp[p*2+1]);
// int ap2=a[b[p*2+1]];
// int ap=a[b[p]];
int bp=b[p];
// int bp2=b[p*2+1];
a[b[p*2+1]]=p;
b[p]=b[p*2+1];
a[bp]=p*2+1;
b[p*2+1]=bp;
DOWN(p*2+1);
}
return ;
}
if(hp[p]>hp[p*2])
{
swap(hp[p], hp[p*2]);
// int ap2=a[b[p*2]];
// int ap=a[b[p]];
int bp=b[p];
// int bp2=b[p*2];
a[b[p*2]]=p;
b[p]=b[p*2];
a[bp]=p*2;
b[p*2]=bp;
DOWN(p*2);
}
if(hp[p]>hp[p*2+1])
{
swap(hp[p], hp[p*2+1]);
// int ap2=a[b[p*2+1]];
// int ap=a[b[p]];
int bp=b[p];
// int bp2=b[p*2+1];
a[b[p*2+1]]=p;
b[p]=b[p*2+1];
a[bp]=p*2+1;
b[p*2+1]=bp;
DOWN(p*2+1);
}
}
int main()
{
/// hp -> heap
/// a -> a[x] == pozitia pe care este elementul intrat al x-lea
/// b -> b[x] == al catelea a intrat numarul de pe pozitia x
freopen("heapuri.in", "r", stdin);
freopen("heapuri.out", "w", stdout);
scanf("%d", &t);
while(t)
{
t--;
scanf("%d", &op);
if(op==3)
{
printf("%d\n", hp[1]);
continue;
}
if(op==1)
{
scanf("%d", &x);
n++;
m++;
hp[n]=x;
b[n]=m;
a[m]=n;
UP(n);
continue;
}
if(op==2)
{
scanf("%d", &x);
hp[a[x]]=hp[n];
ax=a[x];
a[b[n]]=a[x];
b[a[x]]=b[n];
n--;
DOWN(a[x]);
}
}
return 0;
}
/// MultiSet - 100p
/*using namespace std;
int t, op, x, m, a[200005];
multiset <int> hp;
int main()
{
freopen("heapuri.in", "r", stdin);
freopen("heapuri.out", "w", stdout);
scanf("%d", &t);
while(t)
{
t--;
scanf("%d", &op);
if(op==3) printf("%d\n", *hp.begin());
else
{
scanf("%d", &x);
if(op==1)
{
a[++m]=x;
hp.insert(x);
}
else
{
hp.erase(hp.find(a[x]));
}
}
}
return 0;
}*/