백준 1655번 가운데를 말해요 — 힙 C++ 풀이

#include <iostream>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, size = 0;

    priority_queue<int> maxq;
    priority_queue<int, vector<int>, greater<int>> minq;

    cin >> n;

    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;

        if (size == 0) {
            maxq.push(m);
        } else if (size == 1) {
            if (m > maxq.top()) {
                minq.push(m);
            } else {
                minq.push(maxq.top());
                maxq.pop();
                maxq.push(m);
            }
        } else {
            maxq.push(m);

            if (maxq.top() > minq.top()) {
                minq.push(maxq.top());
                maxq.pop();

                if (minq.size() > maxq.size()) {
                    maxq.push(minq.top());
                    minq.pop();
                }
            }

            if (maxq.size() - minq.size() > 1) {
                minq.push(maxq.top());
                maxq.pop();
            }
        }

        cout << maxq.top() << '\n';
        size++;
    }

    return 0;
}