提出 #75852693

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

class Solution {

private:

    priority_queue<long long> leftHeap;

    priority_queue<
        long long,
        vector<long long>,
        greater<long long>
    > rightHeap;

public:

    void insertNumber(long long x) {

        if (leftHeap.empty() || x <= leftHeap.top()) {
            leftHeap.push(x);
        }
        else {
            rightHeap.push(x);
        }

        balanceHeaps();
    }

    void balanceHeaps() {

        while (leftHeap.size() > rightHeap.size() + 1) {

            rightHeap.push(leftHeap.top());
            leftHeap.pop();
        }

        while (rightHeap.size() > leftHeap.size()) {

            leftHeap.push(rightHeap.top());
            rightHeap.pop();
        }
    }

    long long getMedian() {

        return leftHeap.top();
    }
};

int main() {

    long long X, Q;
    cin >> X >> Q;

    Solution obj;

    obj.insertNumber(X);

    for (long long i = 0; i < Q; i++) {

        long long A, B;
        cin >> A >> B;

        obj.insertNumber(A);
        obj.insertNumber(B);

        cout << obj.getMedian() << "\n";
    }

    return 0;
}

提出情報

ジャッジ結果