Cod sursa(job #2894604)

Utilizator RaduAntoneoAntonio Alexandru Radu RaduAntoneo Data 27 aprilie 2022 23:43:05
Problema Heapuri Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
 
static vector<int> heap;
int pozitii[200001];
 
void urca(int poz) {
    while(poz) {
        int tata = (poz - 1) / 2;
        if(heap[tata] > heap[poz]) {
            swap(heap[tata], heap[poz]);
            poz = tata;
        }
        else break;
    }
}
 
void adauga(int x) {
    heap.push_back(x);
    urca(heap.size() - 1);
}
 
void coboara(int poz) {
    int st = poz * 2 + 1;
    int dr = st + 1;
    if(st >= heap.size())
        return;
    if(heap[st] < heap[dr]) {
        if(heap[st] < heap[poz]) {
            swap(heap[poz], heap[st]);
            coboara(st);
        }
    } 
    else if(heap[dr] < heap[poz]) {
        swap(heap[poz], heap[dr]);
        coboara(dr);
        }
    return;
}
 
void sterge(int poz) {
    if(heap.size() == 0)
        return;
    heap[poz] = heap[heap.size() - 1];
    heap.pop_back();
    urca(poz);
    coboara(poz);
}
 
void stergeN(int val) {
    for(int i = 0; i < heap.size(); i++)
        if(val == heap[i]) {
            sterge(i);
            break;
        }
}
 
ifstream f("heapuri.in");
ofstream g("heapuri.out");
#define cin f
#define cout g
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t, op, nr, cnt = 1;
    cin >> t;
    while(t--) {
        cin >> op;
        if(op == 3) cout << heap[0] << '\n';
        else {
            cin >> nr;
            if(op == 1) {adauga(nr); pozitii[cnt++] = nr;}
            else stergeN(pozitii[nr]);
        }
    }
}