結果

問題 No.3298 K-th Slime
ユーザー Astroseek
提出日時 2025-10-05 15:38:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 232 ms / 2,000 ms
コード長 2,076 bytes
コンパイル時間 3,437 ms
コンパイル使用メモリ 290,496 KB
実行使用メモリ 13,184 KB
最終ジャッジ日時 2025-10-05 15:38:44
合計ジャッジ時間 5,979 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(i, r) for(int i = 0; i < (int)(r); i++)
#define reap(i, k, r) for(ll i = (ll)(k); i < (ll)(r); i++)
#define ALL(x) std::begin(x), std::end(x)
#define rALL(x) std::rbegin(x), std::rend(x)
#define MOD 998244353
using namespace std;
int main(){
    ll N, K, Q; cin >> N >> K >> Q;
    map<ll, ll> mp;
    vector<ll> A(N);
    rep(i, N){
        cin >> A[i];
        mp[A[i]]++;
    }
    sort(ALL(A));
    ll cur = A[K - 1];
    ll ko = 0;
    for(auto [l, r] : mp){
        if(l >= cur)break;
        ko += r;
    }
    // auto ch = [&]() -> void {
    //     while(ko >= K){
    //         auto it = mp.lower_bound(cur);
    //         it--;
    //         auto [l, r] = *it;
    //         ko -= r;
    //         cur = l;
    //     }
    //     while(ko + mp[cur] < K){
    //         auto it = mp.lower_bound(cur);
    //         it++;
    //         auto [l, r] = *it;
    //         if(mp[cur] == 0)mp.erase(cur);
    //         cur = l;
    //     }
    // };
    while(Q--){
        ll k; cin >> k;
        if(k == 1){
            ll x; cin >> x;
            mp[x]++;
            if(x < cur){
                ko++;
                if(ko >= K){
                    auto it = mp.lower_bound(cur);
                    it--;
                    auto [l, r] = *it;
                    ko -= r;
                    cur = l;
                }
            }
        }
        if(k == 2){
            ll y; cin >> y;
            mp[cur + y]++;
            if(mp[cur] <= 1){
                auto it = mp.lower_bound(cur);
                it++;
                auto [l, r] = *it;
                mp.erase(cur);
                cur = l;
            }
            else if(mp[cur] + ko <= K){
                auto it = mp.lower_bound(cur);
                it++;
                auto [l, r] = *it;
                mp[cur]--;
                ko += mp[cur];
                cur = l;
            }
            else mp[cur]--;
        }
        if(k == 3){
            cout << cur << endl;
        }
    }
}
0