結果
| 問題 |
No.3298 K-th Slime
|
| コンテスト | |
| ユーザー |
 edon8618
|
| 提出日時 | 2025-11-06 20:58:08 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 194 ms / 2,000 ms |
| コード長 | 10,115 bytes |
| コンパイル時間 | 6,397 ms |
| コンパイル使用メモリ | 336,136 KB |
| 実行使用メモリ | 10,624 KB |
| 最終ジャッジ日時 | 2025-11-06 20:58:19 |
| 合計ジャッジ時間 | 11,009 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define vi vector<int>
#define vl vector<ll>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vc vector<char>
#define ull unsigned long long
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
constexpr ll inf = (1ll << 60);
// const double PI=3.1415926535897932384626433832795028841971;
// ll rui(ll a,ll b){
// if(b==0)return 1;
// if(b%2==1) return a*rui(a*a,b/2);
// return rui(a*a,b/2);
// }
// ll kai(ll n){
// if(n==0)return 1;
// return n*kai(n-1);
// }
using mint = modint998244353;//static_modint<998244353>
// using mint = modint1000000007;//static_modint<1000000007>
// using mint = modint;//mint::set_mod(mod);
// ll const mod=1000000007ll;
// ll const mod=998244353ll;
// ll modrui(ll a,ll b,ll mod){
// a%=mod;
// if(b[i]==0)return 1;
// if(b%2==1) return a*modrui(a*a%mod,b/2,mod)%mod;
// return modrui(a*a%mod,b/2,mod)%mod;
// }
// ll inv(ll x){
// x%=mod;
// return modrui(x,mod-2);
// }
// ll modkai(ll n){
// ll ret=1;
// rep(i,n){
// ret*=(i+1)%mod;
// ret%=mod;
// }
// return ret;
// }
// void incr(vl &v,ll n){// n進法
// ll k=v.size();
// v[k-1]++;
// ll now=k-1;
// while (v[now]>=n)
// {
// v[now]=0;
// if(now==0)break;
// v[now-1]++;
// now--;
// }
// return;
// }
// シンプルなテンプレート AVL 木（set 互換の最小実装）
// - T: キーの型
// - Comp: 比較関数（デフォルト less<T>）
// 提供する主なメソッド:
// insert(const T& key) -> bool (新規挿入なら true)
// erase(const T& key) -> bool (存在して削除できれば true)
// contains(const T& key) -> bool
// lower_bound(const T& key) -> optional<T> (最小の >= key)
// at(int k) -> optional<T> (0-indexed k-th 要素)
// rank(const T& key) -> number of elements < key
// size(), empty(), to_vector()
template <typename T, typename Comp = std::less<T>>
struct AVLTree {
struct Node {
T key;
Node *l = nullptr, *r = nullptr, *p = nullptr;
int height = 1;
int sz = 1;
Node(const T& k): key(k) {}
};
Node* root = nullptr;
Comp comp;
AVLTree() = default;
~AVLTree(){ clear(); }
void clear(){ destroy(root); root = nullptr; }
int size() const { return root ? root->sz : 0; }
bool empty() const { return root == nullptr; }
// --- utilities ---
static int height(Node* x){ return x ? x->height : 0; }
static int sz(Node* x){ return x ? x->sz : 0; }
static void update(Node* x){
if(!x) return;
x->height = 1 + max(height(x->l), height(x->r));
x->sz = 1 + sz(x->l) + sz(x->r);
if(x->l) x->l->p = x;
if(x->r) x->r->p = x;
}
static int bf(Node* x){ return x ? height(x->l) - height(x->r) : 0; }
Node* rotate_right(Node* y){
Node* x = y->l;
Node* b = x->r;
x->r = y; y->l = b;
if(b) b->p = y;
x->p = y->p; y->p = x;
update(y); update(x);
return x;
}
Node* rotate_left(Node* x){
Node* y = x->r;
Node* b = y->l;
y->l = x; x->r = b;
if(b) b->p = x;
y->p = x->p; x->p = y;
update(x); update(y);
return y;
}
// rebalance subtree rooted at x, returns new root of this subtree
Node* rebalance(Node* x){
update(x);
int balance = bf(x);
if(balance > 1){
if(bf(x->l) < 0) x->l = rotate_left(x->l);
return rotate_right(x);
}else if(balance < -1){
if(bf(x->r) > 0) x->r = rotate_right(x->r);
return rotate_left(x);
}
return x;
}
// recursive insert helper, duplicates allowed (insert into right subtree)
pair<Node*, bool> insert_node(Node* node, const T& key){
if(!node) return { new Node(key), true };
if(comp(key, node->key)){
auto pr = insert_node(node->l, key);
node->l = pr.first; if(node->l) node->l->p = node;
}else{
// duplicates also go to right subtree -> multiset 挙動
auto pr = insert_node(node->r, key);
node->r = pr.first; if(node->r) node->r->p = node;
}
node = rebalance(node);
return { node, true };
}
// insert: always inserts (returns true)
bool insert(const T& key){
auto pr = insert_node(root, key);
root = pr.first;
if(root) root->p = nullptr;
return pr.second;
}
// find min in subtree
static Node* find_min(Node* x){ while(x && x->l) x = x->l; return x; }
static Node* find_max(Node* x){ while(x && x->r) x = x->r; return x; }
// erase a key, recursive helper returns new subtree root and whether erased
pair<Node*, bool> erase_node(Node* node, const T& key){
if(!node) return { nullptr, false };
bool erased = false;
if(comp(key, node->key)){
auto pr = erase_node(node->l, key);
node->l = pr.first; if(node->l) node->l->p = node;
erased = pr.second;
}else if(comp(node->key, key)){
auto pr = erase_node(node->r, key);
node->r = pr.first; if(node->r) node->r->p = node;
erased = pr.second;
}else{
erased = true;
// node to delete
if(!node->l || !node->r){
Node* tmp = node->l ? node->l : node->r;
if(!tmp){
// no child
delete node;
return { nullptr, true };
}else{
tmp->p = node->p;
delete node;
return { tmp, true };
}
}else{
// two children: replace with successor
Node* succ = find_min(node->r);
node->key = succ->key;
auto pr = erase_node(node->r, succ->key);
node->r = pr.first; if(node->r) node->r->p = node;
}
}
node = rebalance(node);
return { node, erased };
}
// erase a single occurrence
bool erase(const T& key){
auto pr = erase_node(root, key);
root = pr.first;
if(root) root->p = nullptr;
return pr.second;
}
// erase all occurrences of key, return number removed
int erase_all(const T& key){
int cnt = 0;
while(erase(key)) ++cnt;
return cnt;
}
bool contains(const T& key) const {
Node* cur = root;
while(cur){
if(comp(key, cur->key)) cur = cur->l;
else if(comp(cur->key, key)) cur = cur->r;
else return true;
}
return false;
}
// count occurrences of key
int count(const T& key) const {
// number of elements < key と < upper_bound の差で求める
int lo = rank(key);
optional<T> ub = upper_bound(key);
int hi = ub ? rank(*ub) : size();
return hi - lo;
}
// lower_bound: smallest key >= given key
optional<T> lower_bound(const T& key) const {
Node* cur = root;
Node* ans = nullptr;
while(cur){
if(!comp(cur->key, key)){ // cur->key >= key
ans = cur;
cur = cur->l;
}else cur = cur->r;
}
if(ans) return ans->key;
return nullopt;
}
// upper_bound: smallest key > given key
optional<T> upper_bound(const T& key) const {
Node* cur = root;
Node* ans = nullptr;
while(cur){
if(comp(key, cur->key)){ // key < cur->key => cur->key > key
ans = cur;
cur = cur->l;
} else {
cur = cur->r;
}
}
if(ans) return ans->key;
return nullopt;
}
// k-th (0-indexed). return optional
optional<T> at(int k) const {
if(k < 0 || k >= size()) return nullopt;
Node* cur = root;
while(cur){
int lsz = sz(cur->l);
if(k < lsz) cur = cur->l;
else if(k == lsz) return cur->key;
else { k -= lsz + 1; cur = cur->r; }
}
return nullopt;
}
// number of elements strictly less than key
int rank(const T& key) const {
int r = 0;
Node* cur = root;
while(cur){
if(comp(key, cur->key)){
cur = cur->l;
}else{
if(!comp(cur->key, key)) { // cur->key >= key
cur = cur->l;
} else {
r += 1 + sz(cur->l);
cur = cur->r;
}
}
}
return r;
}
// inorder to vector
void inorder(Node* t, vector<T>& out) const {
if(!t) return;
inorder(t->l, out);
out.push_back(t->key);
inorder(t->r, out);
}
vector<T> to_vector() const {
vector<T> v; v.reserve(size());
inorder(root, v);
return v;
}
private:
void destroy(Node* t){
if(!t) return;
destroy(t->l);
destroy(t->r);
delete t;
}
};
void solve(){
AVLTree<ll> st;
ll n,k,q;
cin >> n >> k >> q;
--k;
rep(i,n){
ll a;
cin >> a;
st.insert(a);
}
while(q--){
ll op,x;
cin >> op;
if(op==1){
cin >> x;
st.insert(x);
}
if(op==2){
cin >> x;
ll s=*st.at(k);
st.erase(s);
st.insert(s+x);
}
if(op==3){
cout << *st.at(k) << endl;
}
}
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
ll t = 1;
// cin >> t;
while (t--) solve();
}