結果

問題 No.649 ここでちょっとQK！
ユーザー log_Klog_K
提出日時 2023-11-02 00:58:19
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

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