結果

問題 No.3298 K-th Slime
ユーザー Hydrogen
提出日時 2025-10-05 16:20:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 380 ms / 2,000 ms
コード長 6,314 bytes
コンパイル時間 3,144 ms
コンパイル使用メモリ 287,264 KB
実行使用メモリ 145,920 KB
最終ジャッジ日時 2025-10-05 16:20:42
合計ジャッジ時間 6,948 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128_t;
using uc = unsigned char;
#define Max(X,Y) (((X) > (Y)) ? (X) : (Y))
#define Min(X,Y) (((X) < (Y)) ? (X) : (Y))
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define YES yes return 0;
#define NO no return 0;
#define pc cout << count << endl;
#define PC pc return 0;
#define INF 0x1fffffff
#define LINF 0x1fffffffffffffff
#define Eps LDBL_EPSILON
#ifdef DEBUG
#define dbg(X) cerr << X << endl
#else
#define dbg(...)
#endif

template <typename T>
inline ostream& operator<<(ostream& os, const vector<T>& v) noexcept {
    if(!v.empty()) os << v[0];
    for(size_t i = 1; i < v.size(); i++) os << " " << v[i];
    return os;
}

template <typename T>
void swap(T& a, T& b) {
    auto x = a;
    a = b;
    b = x;
}

template <typename T>
size_t partition(vector<T>& list, size_t start, size_t end) {
    auto pivot = list[end-1];
    auto hi = start;
    for(auto i = start; i < end - 1; i++) {
        if(list[i] <= pivot) {
            swap(list[hi], list[i]);
            hi++;
        }
    }
    swap(list[hi], list[end-1]);
    return hi;
}

template <typename T>
void quicksort(vector<T>& list, size_t l, size_t r) {
    if(l < r) {
        auto pivot = partition(list, l, r);
        quicksort(list, l, pivot);
        quicksort(list, pivot + 1, r);
    }
}

struct string_set {
    map<size_t, vector<string_view>> registry = {};
    bool contains(string_view s) {
        auto h = hash<string_view>()(s);
        return registry.contains(h)
                && find(registry[h].begin(), registry[h].end(), s) != registry[h].end();
    }
    void add(string_view s) {
        auto h = hash<string_view>()(s);
        auto pos = find(registry[h].begin(), registry[h].end(), s);
        if(pos != registry[h].end()) return;
        registry[h].push_back(s);
    }
    void remove(string_view s) {
        auto h = hash<string_view>()(s);
        if(!registry.contains(h)) return;
        auto pos = find(registry[h].begin(), registry[h].end(), s);
        if(pos == registry[h].end()) return;
        registry[h].erase(pos);
    }
};

template <typename T>
struct BIT {
    ll n;
    vector<T> tree;
    BIT(ll size) : n(size + 1), tree(n, 0) {}
    void add(ll i, T x) {
        for (ll idx = i; idx < n; idx += (idx & -idx)) {
            tree[idx] += x;
        }
    }
    T sum(ll i) {
        T s(0);
        for (ll idx = i; idx > 0; idx -= (idx & -idx)) {
            s += tree[idx];
        }
        return s;
    }
};

struct RSQ {
    ll N;
    vector<ll> tree;
    RSQ(ll max) : N(), tree(max*4, 0) {
        ll x = 1;
        while(max > x) x*=2;
        N = x;
    }
    void inc(ll i) {
        i += N - 1;
        tree[i]++;
        while (i > 0) {
            i = (i - 1) / 2;
            tree[i]++;
        }
    }
    ll find(ll k) {
        auto [cod, num] = find_sect(k, 0);
        if(cod) return num;
        return -1;
    }
    pair<bool,ll> find_sect(ll k, ll n) {
        if(n >= N-1) {
            if(tree[n] < k) {
                return {false, k - tree[n]};
            }
            return {true, n-N-1};
        }
        if(tree[n] < k) return {false, k - tree[n]};
        auto [cod, num] = find_sect(k, 2*n+1);
        if(cod) {
            return {cod, num};
        }
        return find_sect(k-num, 2*n+2);
    }
};

template<typename U = ull, ll B = 64>
class binary_trie {
    struct node {
        int cnt;
        node *ch[2];
        node() : cnt(0), ch{ nullptr, nullptr } {}
    };
    node* add(node* t, U val, int b = B - 1) {
        if (!t) t = new node;
        t->cnt += 1;
        if (b < 0) return t;
        bool f = (val >> (U)b) & (U)1;
        t->ch[f] = add(t->ch[f], val, b - 1);
        return t;
    }
    node* sub(node* t, U val, int b = B - 1) {
        assert(t);
        t->cnt -= 1;
        if (t->cnt == 0) return nullptr;
        if (b < 0) return t;
        bool f = (val >> (U)b) & (U)1;
        t->ch[f] = sub(t->ch[f], val, b - 1);
        return t;
    }
    U get_min(node* t, U val, int b = B - 1) const {
        assert(t);
        if (b < 0) return 0;
        bool f = (val >> (U)b) & (U)1; f ^= !t->ch[f];
        return get_min(t->ch[f], val, b - 1) | ((U)f << (U)b);
    }
    U get(node* t, int k, int b = B - 1) const {
        if (b < 0) return 0;
        int m = t->ch[0] ? t->ch[0]->cnt : 0;
        return k < m ? get(t->ch[0], k, b - 1) : get(t->ch[1], k - m, b - 1) | ((U)1 << (U)b);
    }
    int count_lower(node* t, U val, int b = B - 1) {
        if (!t || b < 0) return 0;
        bool f = (val >> (U)b) & (U)1;
        return (f && t->ch[0] ? t->ch[0]->cnt : 0) + count_lower(t->ch[f], val, b - 1);
    }
    node *root;
public:
    binary_trie() : root(nullptr) {}
    int size() const {
        return root ? root->cnt : 0;
    }
    bool empty() const {
        return !root;
    }
    void insert(U val) {
        root = add(root, val);
    }
    void erase(U val) {
        root = sub(root, val);
    }
    U max_element(U bias = 0) const {
        return get_min(root, ~bias);
    }
    U min_element(U bias = 0) const {
        return get_min(root, bias);
    }
    int lower_bound(U val) { // return id
        return count_lower(root, val);
    }
    int upper_bound(U val) { // return id
        return count_lower(root, val + 1);
    }
    U operator[](int k) const {
        assert(0 <= k && k < size());
        return get(root, k);
    }
    int count(U val) const {
        if (!root) return 0;
        node *t = root;
        for (int i = B - 1; i >= 0; i--) {
            t = t->ch[(val >> (U)i) & (U)1];
            if (!t) return 0;
        }
        return t->cnt;
    }
};

int main() {
    cin.tie(nullptr);

    ll N, K, Q;
    cin >> N >> K >> Q;
    binary_trie A;
    for(ll i = 0; i < N; i++) {
        ull a;
        cin >> a;
        A.insert(a);
    }
    for(; Q>0; Q--) {
        int q;
        cin >> q;
        if(q == 1) {
            ll x;
            cin >> x;
            A.insert(x);
        } else if(q == 2) {
            ll y;
            cin >> y;
            ull pl = A[K-1];
            A.erase(pl);
            A.insert(pl+y);
        } else {
            cout << A[K-1] << endl;
        }
    }
}
0