11286번: 절대값 힙

https://www.acmicpc.net/problem/11286


$O(n\lg n)$

우선순위 큐를 이용한다.

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<pair<int, int> > pq;
int n, x;
int main() {
    for (scanf("%d", &n); n--;) {
        scanf("%d", &x);
        if (x) pq.push({ -abs(x),-x });
        else if (pq.empty()) puts("0");
        else printf("%d\n", -pq.top().second), pq.pop();
    }
    return 0;
}