Submission #5930963


Source Code Expand

Copy
#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

Submission Time
Task F - Absolute Minima
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2208 Byte
Status
Exec Time 304 ms
Memory 3828 KB

Test Cases

Set Name Score / Max Score Test Cases
All 600 / 600 bilateral_minima, many_dup_01, many_dup_02, max_val, min_val, random_max_01, random_max_02, random_max_03, random_max_04, random_max_05, random_max_06, random_max_07, random_small_01, random_small_02, random_small_03, random_small_04, random_small_05, random_small_06, random_small_07, random_small_08, sample_01, sample_02
Sample 0 / 0 sample_01, sample_02
Case Name Status Exec Time Memory
bilateral_minima 304 ms 3828 KB
many_dup_01 181 ms 2428 KB
many_dup_02 218 ms 2640 KB
max_val 208 ms 2036 KB
min_val 220 ms 2036 KB
random_max_01 262 ms 3016 KB
random_max_02 276 ms 3128 KB
random_max_03 283 ms 3260 KB
random_max_04 221 ms 2684 KB
random_max_05 177 ms 2128 KB
random_max_06 296 ms 3512 KB
random_max_07 293 ms 3572 KB
random_small_01 2 ms 256 KB
random_small_02 2 ms 256 KB
random_small_03 2 ms 256 KB
random_small_04 2 ms 256 KB
random_small_05 2 ms 256 KB
random_small_06 2 ms 256 KB
random_small_07 2 ms 256 KB
random_small_08 3 ms 256 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB