Submission #5930963

---

Source Code Expand

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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

template<typename T>
using reversed_priority_queue = \
    std::priority_queue<T, std::vector<T>, std::greater<T> >;

signed main() {
    ll Q;
    cin>>Q;

    ll suma = 0;
    ll sumb = 0;
    priority_queue<ll> ql; // 中央値の左側部分
    reversed_priority_queue<ll> qr; // 中央値の右側部分

    ql.push(-3000000000);
    qr.push(3000000000);

    rep(i,0,Q){
        ll q;
        cin>>q;
        if (q == 1) {
            // 更新クエリ
            ll a, b;
            cin>>a>>b;
            sumb+=b;
            if (ql.size() == qr.size()) {
                // 奇数個目の追加
                if (ql.top() <= a && a <= qr.top()) {
                    ; // 最小区間内への追加なのでsumaの増分はなし
                } else {
                    // 最小区間外への追加なので、sumaは近いほうとの差分を追加
                    suma += min(abs(ql.top()-a), abs(qr.top()-a));
                }
            } else {
                // 偶数個目の追加
                // 単純に中央値との差分
                suma += abs(ql.top() - a);
            }

            if (a <= ql.top()) {
                ql.push(a); 
            } else {
                qr.push(a); 
            }
            // cout<<"hoge: "<<suma<<endl;

            if (!( ql.size() == qr.size() || ql.size() == qr.size() + 1)) {
                // キューを整理
                if (qr.size() > ql.size()) {
                    // 右側に追加しすぎ
                    // ql.size() + 1 == qr.size() になってしまっている
                    ql.push(qr.top());
                    qr.pop();
                } else {
                    // 左側に追加しすぎ
                    qr.push(ql.top());
                    ql.pop();
                }
            }
        } else {
            // 求値クエリ
            cout<<ql.top()<<" "<<suma+sumb<<endl;
        }
    }
    return 0;
}

Submission Info

Judge Result