14235 - 크리스마스 선물

 

14235번: 크리스마스 선물

 

#include <stdio.h>

int N;
int A;

const int LN = 5e5 + 10;

int maxComp(int x, int y) { return x > y; }
void swap(int& x, int& y) { int z = x; x = y; y = z; }

struct PQ {
  int hn;
  int heap[LN];
  int (*comp)(int, int);

  void init() {
    hn = 0;
    comp = maxComp;
  }

  void push(int x) {
    heap[++hn] = x;

    for (int c = hn; c > 1; c /= 2) {
      if (comp(heap[c], heap[c / 2])) { swap(heap[c / 2], heap[c]); }
      else break;
    }
  }

  int pop() {
    swap(heap[1], heap[hn--]);

    for (int c = 2; c <= hn; c *= 2) {
      if (c < hn && comp(heap[c + 1], heap[c]))  { ++c; }
      if (comp(heap[c], heap[c / 2])) { swap(heap[c / 2], heap[c]); }
      else break;
    }

    return heap[hn + 1];
  }
} maxpq;

void init() {
  maxpq.init();

  scanf("%d", &N);
}

void calculateAndPrint() {
  for (int n = 0; n < N; ++n) {
    scanf("%d", &A);

    if (A) {
      int t;

      for (int a = 0; a < A; ++a) {
        scanf("%d", &t);

        maxpq.push(t);
      }
    } else {
      printf("%d\n", maxpq.hn ? maxpq.pop() : -1);
    }
  }
}

int main(void) {
  // freopen("14235.txt", "r", stdin);

  init();

  calculateAndPrint();

  return 0;
}

 

이제 끝내자 힙