結果

問題 No.3298 K-th Slime
ユーザー mele
提出日時 2025-10-05 14:52:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,083 bytes
コンパイル時間 1,893 ms
コンパイル使用メモリ 196,288 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-05 14:53:41
合計ジャッジ時間 4,135 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FFOR(i,a,b) for (ll i = (b); i >= (a); i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) FFOR(i,0,n)
#define YES cout << "Yes" << endl
#define NO cout << "No" << endl
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 1LL<<60;
const int MOD = 100000000;

class fenwick_tree_set {
    const int n;
    int cnt;
    vector<int> data;
    int find(int p) const {
        int res = 0;
        while (p > 0) {
            res += data[p];
            p -= p & -p;
        }
        return res;
    }
    void add(int p, int x) {
        ++p;
        while (p <= n) {
            data[p] += x;
            p += p & -p;
        }
    }
public:
    fenwick_tree_set(int maxi)
        : n(maxi + 1), cnt(0), data(n + 1) {}
    int size() const {
        return cnt;
    }
    int count(int val) const {
        return find(val + 1) - find(val);
    }
    void insert(int val) {
        add(val, 1);
        cnt += 1;
    }
    void erase(int val) {
        add(val, -1);
        cnt -= 1;
    }
    int kth_element(int k) const {
        int p = 1 << (32 - __builtin_clz(n)), res = 0;
        while (p >>= 1) {
            if (res + p <= n && data[res + p] <= k) {
                k -= data[res + p];
                res += p;
            }
        }
        return res;
    }
};

int main(){
    int N,K,Q,q,x,a;
    cin>>N>>K>>Q;
    fenwick_tree_set f(N);
    rep(i,N){
        cin>>a;
        f.insert(a);
    }

    rep(i,Q){
        cin>>q;
        if(q==1){
            cin>>x;
            f.insert(x);
        }else if(q==2){
            cin>>x;
            int kk = f.kth_element(K-1);
            f.erase(kk);
            f.insert(kk+x);
        }else{
            int kk = f.kth_element(K-1);
            cout<<kk<<endl;
        }
    }
    return 0;
}
0