結果

問題 No.3298 K-th Slime
ユーザー Hydrogen
提出日時 2025-10-05 15:17:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,339 bytes
コンパイル時間 3,306 ms
コンパイル使用メモリ 287,956 KB
実行使用メモリ 15,944 KB
最終ジャッジ日時 2025-10-05 15:18:55
合計ジャッジ時間 14,681 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other WA * 14 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

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 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);
    }
};

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

    ll N, K, Q;
    cin >> N >> K >> Q;
    vector<ll> A;
    A.reserve(N+Q);
    for(ll i = 0; i < N; i++) {
        ll a;
        cin >> a;
        A.push_back(a);
    }
    sort(A.begin(), A.end());
    for(; Q>0; Q--) {
        int q;
        cin >> q;
        if(q == 1) {
            ll x;
            cin >> x;
            A.push_back(x);
            for(ll i = A.size()-1; i > 0; i--) {
                if(A[i-1] > x) {
                    A[i] = A[i-1];
                    A[i-1] = x;
                } else break;
            }
        } else if(q == 2) {
            ll y;
            cin >> y;
            ll pl = A[K-1]+y;
            for(ll i = K-1; i < A.size()-1; i++) {
                if(A[i+1] < pl) {
                    A[i] = A[i+1];
                    A[i+1] = pl;
                } else break;
            }
        } else {
            cout << A[K-1] << endl;
        }
    }
}
0