結果

問題 No.3298 K-th Slime
ユーザー Today03
提出日時 2025-10-05 13:56:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 209 ms / 2,000 ms
コード長 5,056 bytes
コンパイル時間 4,139 ms
コンパイル使用メモリ 325,916 KB
実行使用メモリ 13,440 KB
最終ジャッジ日時 2025-10-05 13:56:51
合計ジャッジ時間 6,181 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define REP(i,n) for(int i=0; i<n; i++)
bool chmax(auto& a, auto b) { return a<b ? a=b, true : false; }
bool chmin(auto& a, auto b) { return a>b ? a=b, true : false; }
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;

#ifdef DEBUG
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif


#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
struct SortedMultiTree:tree<pair<T,int>,null_type,less<pair<T,int>>,rb_tree_tag,tree_order_statistics_node_update> {
    using tree<pair<T,int>,null_type,less<pair<T,int>>,rb_tree_tag,tree_order_statistics_node_update>::tree;
    using P=pair<T,int>;
    T not_found=-1;
    SortedMultiTree()=default;

    /// @brief コンストラクタ
    /// @param not_found 指定の値が見つからなかったときに返す値
    SortedMultiTree(T not_found=-1) { this->not_found=not_found; }

	/// @brief x を追加する
    void add(T x) {
        if(this->size()==0) {
            this->insert(P{x,0});
            return;
        }
        auto itr=this->lower_bound(P{x+1,0});
        if(itr==this->begin()) {
            this->insert(P{x,0});
            return;
        }
        itr--;
        if(itr->first!=x) {
            this->insert(P{x,0});
            return;
        }
        this->insert(P{x,itr->second+1});
    }

    /// @brief 最小値を返す
    T min() {
        if(this->empty())return not_found;
        return*this->begin()->first;
    }

    /// @brief 最大値を返す
    T max() {
        if(this->empty())return not_found;
        return*this->rbegin()->first;
    }

    /// @brief 最小値を返し、削除する
    T pop_min() {
        if(this->empty())return not_found;
        auto mn=*this->begin();
        T ret=mn.first;
        this->erase(mn);
        return ret;
    }

    /// @brief 最大値を返し、削除する
    T pop_max() {
        if(this->empty())return not_found;
        auto mx=*this->rbegin();
        T ret=mx.first;
        this->erase(mx);
        return ret;
    }

    /// @brief x が含まれているか否かを返す
    bool contains(T x) {
        auto itr=this->lower_bound({x,0});
        if(itr==this->end())return false;
        return itr->first==x;
    }

	/// @brief x の個数を返す
    int count(T x) {
        if(!contains(x))return 0;
        auto itr=this->lower_bound({x+1,0});
        itr--;
        return itr->second+1;
    }

    /// @brief x を削除する
	/// @brief x が含まれていたか否かを返す
    bool discard(T x) {
        if(!contains(x))return false;
        auto itr=prev(this->lower_bound({x+1,0}));
        if(itr==this->end())return false;
        this->erase(itr);
        return true;
    }

	/// @brief x より大きい最小の値を返す
    T gt(T x) {
        auto itr=this->lower_bound({x+1,0});
        if(itr==this->end())return not_found;
        return itr->first;
    }

	/// @brief x 以上最小の値を返す
    T ge(T x) {
        auto itr=this->lower_bound({x,0});
        if(itr==this->end())return not_found;
        return itr->first;
    }

	/// @brief x 未満最大の値を返す
    T lt(T x) {
        auto itr=this->lower_bound({x,0});
        if(itr==this->begin())return not_found;
        return(--itr)->first;
    }

	/// @brief x 以下最大の値を返す
    T le(T x) {
        auto itr=this->lower_bound({x+1,0});
        if(itr==this->begin())return not_found;
        return(--itr)->first;
    }

    /// @brief x 未満の値の個数を返す
    int count_lt(T x) { return this->order_of_key({x,0}); }

    /// @brief x 以下の値の個数を返す
    int count_le(T x) { return this->order_of_key({x+1,0}); }

    /// @brief x より大きい値の個数を返す
    int count_gt(T x) { return this->size()-this->order_of_key({x+1,0}); }

    /// @brief x 以上の値の個数を返す
    int count_ge(T x) { return this->size()-this->order_of_key({x,0}); }

    /// @brief k(0-indexed) 番目に小さい値の個数を返す
    T kth_min(int k) { return this->find_by_order(k)->first; }

    /// @brief k(0-indexed) 番目に大きい値の個数を返す
    T kth_max(int k) { return this->find_by_order(this->size()-k-1)->first; }
};

//----------------------------------------------------------

void solve() {
    int N,K,Q; cin>>N>>K>>Q;
    vector<ll> A(N); REP(i,N) cin>>A[i];
    SortedMultiTree<ll> st(-1);
    REP(i,N) st.add(A[i]);

    while(Q--) {
        int t; cin>>t;
        if(t==1) {
            ll x; cin>>x;
            st.add(x);
        } else if(t==2) {
            ll y; cin>>y;
            ll x=st.kth_min(K-1);
            st.discard(x);
            st.add(x+y);
        } else {
            ll x=st.kth_min(K-1);
            cout<<x<<'\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //cout<<fixed<<setprecision(15);
    int T=1; //cin>>T;
    while(T--) solve();
}
0