結果

問題 No.649 ここでちょっとQK！
ユーザー log_Klog_K
提出日時 2023-11-02 00:58:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 278 ms / 3,000 ms
コード長 2,358 bytes
コンパイル時間 2,048 ms
コンパイル使用メモリ 209,444 KB
実行使用メモリ 12,800 KB
最終ジャッジ日時 2024-09-25 18:03:46
合計ジャッジ時間 8,954 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 266 ms
6,816 KB
testcase_04 AC 278 ms
12,800 KB
testcase_05 AC 217 ms
12,800 KB
testcase_06 AC 218 ms
12,800 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 113 ms
7,168 KB
testcase_13 AC 113 ms
7,168 KB
testcase_14 AC 113 ms
7,168 KB
testcase_15 AC 129 ms
7,296 KB
testcase_16 AC 118 ms
7,680 KB
testcase_17 AC 137 ms
7,936 KB
testcase_18 AC 155 ms
8,320 KB
testcase_19 AC 166 ms
8,576 KB
testcase_20 AC 185 ms
8,960 KB
testcase_21 AC 194 ms
9,344 KB
testcase_22 AC 216 ms
9,728 KB
testcase_23 AC 224 ms
10,112 KB
testcase_24 AC 241 ms
10,496 KB
testcase_25 AC 262 ms
11,008 KB
testcase_26 AC 278 ms
11,264 KB
testcase_27 AC 3 ms
6,940 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 3 ms
6,944 KB
testcase_30 AC 82 ms
7,168 KB
testcase_31 AC 91 ms
7,552 KB
testcase_32 AC 2 ms
6,944 KB
testcase_33 AC 2 ms
6,940 KB
testcase_34 AC 2 ms
6,944 KB
testcase_35 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "verify/yuki-649.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/649"

#line 1 "library/DataStructure/K-th_MultiSet.hpp"
#include <bits/stdc++.h>
using namespace std;

template<typename Data, typename Value = Data>
struct Kth_MultiSet{
    using F = function<Value(Value, Data)>;
    using G = function<bool(Data, Data)>;

    private:
    int __K;
    multiset<Data> __P, __Q;
    F __Add, __Sub;
    G __Require;
    Value __Sum;

    void balance(){
        while(__P.size() < __K && __Q.size()){
            auto itr = __Q.begin();
            __Sum = __Add(__Sum, *itr);
            __P.insert(*itr);
            __Q.erase(itr);
        }
        if(__P.empty() || __Q.empty()) return;
        while(1){
            auto si = --(__P.end());
            auto li = __Q.begin();
            Data sv = (*si), lv = (*li);
            if(__Require(sv, lv)) break;
            __Sum = __Add(__Sub(__Sum, sv), lv);
            __P.erase(si), __Q.erase(li);
            __P.insert(lv), __Q.insert(sv);
        }
    }

    public:
    Kth_MultiSet(int K, 
        F Add = [](Value x, Data y){return x + y;}, 
        F Sub = [](Value x, Data y){return x - y;},
        G Require = [](Data x, Data y){return x <= y;})
        : __K(K), __Add(Add), __Sub(Sub), __Require(Require), __Sum(){}

    void insert(Data data){
        __Q.insert(data);
        balance();
    }

    void erase(Data value){
        auto itr = __P.find(value);
        if(itr != __P.end()){
            __Sum = __Sub(__Sum, value);
            __P.erase(itr);
        }
        else{
            assert(__Q.find(value) != __Q.end());
            __Q.erase(__Q.find(value));
        }
        balance();
    }

    inline bool exist(){
        return __P.size() == __K;
    }

    inline Data get(){
        assert(exist());
        return *(--(__P.end()));
    }

    inline Value sum(){
        return __Sum;
    }
};
#line 4 "verify/yuki-649.test.cpp"

int main(){
    int Q, K; cin >> Q >> K;
    Kth_MultiSet<long long> st(K);
    while(Q--){
        int query; cin >> query;
        if(query == 1){
            long long v; cin >> v;
            st.insert(v);
        }
        else{
            long long v = -1;
            if(st.exist()){
                v = st.get();
                st.erase(v);
            }
            cout << v << endl;
        }
    }
}
0