Cod sursa(job #2792294)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 1 noiembrie 2021 13:22:03
Problema Heapuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("heapuri.in");
ofstream fout("heapuri.out");

struct Heap {
  vector<int> h{0}, entry{0}, pos{0};

  void swapNodes(int u, int v) {
    swap(h[u], h[v]);
    swap(pos[entry[u]], pos[entry[v]]);
    swap(entry[u], entry[v]);
  }

  void upHeap(int v) {
    while (1 < v && h[v] < h[v >> 1]) {
      swapNodes(v, v >> 1);
      v >>= 1;
    }
  }

  void Insert(int x) {
    entry.emplace_back(pos.size());
    pos.emplace_back(h.size());
    h.emplace_back(x);
    upHeap(h.size() - 1);
  }

  void EraseMin() {
    swapNodes(1, h.size() - 1);
    h.pop_back();
    entry.pop_back();
    int v = 1;
    while ((v << 1) < (int)h.size()) {
      int son = v << 1;
      if ((son | 1) < (int)h.size() && h[son | 1] < h[son]) {
        son |= 1;
      }
      if (h[v] <= h[son]) {
        break;
      }
      swapNodes(v, son);
      v = son;
    }
  }

  void Erase(int k) {
    int v = pos[k];
    h[v] = -1;
    upHeap(v);
    EraseMin();
  }

  int getMin() {
    return h[1];
  }
};

void TestCase() {
  int n;
  fin >> n;
  Heap h;
  for (int i = 1; i <= n; ++i) {
    int op;
    fin >> op;
    if (op <= 2) {
      int k;
      fin >> k;
      if (op == 1) {
        h.Insert(k);
      } else {
        h.Erase(k);
      }
    } else {
      fout << h.getMin() << '\n';
    }
  }
}

int main() {
  int tests = 1;
  for (int tc = 1; tc <= tests; ++tc) {
    TestCase();
  }
  fin.close();
  fout.close();
  return 0;
}