Cod sursa(job #3371356)

Utilizator JenJenCristache Ion JenJen Data 29 octombrie 2026 21:27:31
Problema Heapuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
using namespace std;

ifstream cin ("heapuri.in");
ofstream cout ("heapuri.out");

int n, tip, x;
int cnt;
int poz;
int v[200005];
int heap[200005];
int ppoz[200005];
int nr_elem;

void swapp(int a, int b)
{
    swap(ppoz[heap[a]], ppoz[heap[b]]);
    swap(heap[a], heap[b]);
}

void in_sus(int p)
{
    while (p > 1 && v[heap[p]] < v[heap[p >> 1]])
    {
        swapp(p, p >> 1);
        p >>= 1;
    }
}

void in_jos(int p)
{
    int minn = p;

    int st = (p << 1);
    int dr = (p << 1 | 1);

    if (st <= nr_elem && v[heap[st]] < v[heap[minn]])
    {
        minn = st;
    }
    if (dr <= nr_elem && v[heap[dr]] < v[heap[minn]])
    {
        minn = dr;
    }

    if (minn != p)
    {
        swapp(p, minn);
        in_jos(minn);
    }
}

void solve(int p)
{
    if (p == nr_elem)
    {
        nr_elem--;
    } else
    {
        heap[p] = heap[nr_elem];
        nr_elem--;

        ppoz[heap[p]] = p;
        in_sus(p);
        in_jos(p);
    }
}
int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> tip;
        if (tip == 1)
        {
            cin >> x;
            poz++;
            nr_elem++;
            v[poz] = x;
            heap[nr_elem] = poz;
            ppoz[poz] = nr_elem;
            in_sus(nr_elem);
        } else if (tip == 2)
        {
            cin >> x;
            solve(ppoz[x]);
        } else
        {
            cout << v[heap[1]] << '\n';
        }
    }
    return 0;
}