結果

問題 No.649 ここでちょっとQK！
ユーザー log_Klog_K
提出日時 2023-11-02 00:58:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 342 ms / 3,000 ms
コード長 2,358 bytes
コンパイル時間 2,517 ms
コンパイル使用メモリ 210,128 KB
実行使用メモリ 13,004 KB
最終ジャッジ日時 2023-11-02 00:58:31
合計ジャッジ時間 11,698 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 288 ms
4,348 KB
testcase_04 AC 292 ms
13,004 KB
testcase_05 AC 227 ms
13,004 KB
testcase_06 AC 230 ms
13,004 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 136 ms
7,388 KB
testcase_13 AC 139 ms
7,388 KB
testcase_14 AC 139 ms
7,356 KB
testcase_15 AC 142 ms
7,428 KB
testcase_16 AC 145 ms
7,796 KB
testcase_17 AC 167 ms
8,052 KB
testcase_18 AC 186 ms
8,436 KB
testcase_19 AC 204 ms
8,772 KB
testcase_20 AC 231 ms
9,172 KB
testcase_21 AC 245 ms
9,524 KB
testcase_22 AC 266 ms
9,936 KB
testcase_23 AC 279 ms
10,280 KB
testcase_24 AC 315 ms
10,676 KB
testcase_25 AC 323 ms
11,052 KB
testcase_26 AC 342 ms
11,400 KB
testcase_27 AC 3 ms
4,348 KB
testcase_28 AC 3 ms
4,348 KB
testcase_29 AC 3 ms
4,348 KB
testcase_30 AC 104 ms
7,380 KB
testcase_31 AC 120 ms
7,656 KB
testcase_32 AC 2 ms
4,348 KB
testcase_33 AC 2 ms
4,348 KB
testcase_34 AC 2 ms
4,348 KB
testcase_35 AC 2 ms
4,348 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