Pagini recente » Rezultatele filtrării | Cod sursa (job #3220202)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heapuri.in");
ofstream fout("heapuri.out");
int salvare_pozitie[200005];
int salvare_pozitie_introducere[200005];
int heap[200005];
int op;
int n, k, m;
void make_heap(int nod)
{
while (nod > 1)
{
int p = nod / 2;
if (heap[p] < heap[nod])
return;
else
{
swap(heap[p], heap[nod]);
swap(salvare_pozitie[salvare_pozitie_introducere[p]], salvare_pozitie[salvare_pozitie_introducere[nod]]);
swap(salvare_pozitie_introducere[salvare_pozitie[p]],salvare_pozitie_introducere[salvare_pozitie[nod]]);
nod = p;
}
}
}
void remake_heap(int nod)
{
while (2 * nod <= k)
{
int p = 2 * nod;
if (p + 1 <= k && heap[p + 1] < heap[p])
p++;
if (heap[nod] < heap[p])
return;
else
{
swap(heap[nod], heap[p]);
swap(salvare_pozitie[salvare_pozitie_introducere[p]], salvare_pozitie[salvare_pozitie_introducere[nod]]);
swap(salvare_pozitie_introducere[salvare_pozitie[p]],salvare_pozitie_introducere[salvare_pozitie[nod]]);
nod=p;
}
}
}
int main()
{
fin >> m;
for (; m--;)
{
fin >> op;
if (op == 1)
{
int x;
n++;
fin >> x;
salvare_pozitie[n] = ++k;
salvare_pozitie_introducere[k] = n;
heap[k] = x;
make_heap(k);
}
else if (op == 2)
{
int x;
fin >> x;
heap[salvare_pozitie[x]] = heap[k];
salvare_pozitie_introducere[salvare_pozitie[x]]=salvare_pozitie_introducere[salvare_pozitie[heap[k]]];
k--;
remake_heap(salvare_pozitie[x]);
}
else fout<<heap[1]<<'\n';
}
}