#1126184 (C++23) No.3298 K-th Slime

• 問題: No.3298 K-th Slime
• ユーザー: edon8618
• 提出日時: 2025-10-05 16:22:30
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 9,682 bytes
• コンパイル時間: 4,635 ms
• コンパイル使用メモリ: 334,904 KB
• 実行使用メモリ: 11,648 KB
• 最終ジャッジ日時: 2025-10-05 16:22:37
• 合計ジャッジ時間: 7,108 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 2
other	AC * 15 WA * 8 RE * 2

ソースコード

// # pragma GCC target("avx2")
// # pragma GCC optimize("O3")
// # pragma GCC optimize("unroll-loops")

#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)

ll inf = (1ll << 61);
// const double PI=3.1415926535897932384626433832795028841971;

// ll rui(ll a,ll b){
//     if(b[i]==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);
// using mint1=static_modint<998244352>;

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







//https://tjkendev.github.io/procon-library/cpp/binary_search_tree/avl-tree.html

template<typename T>
class AVLTree {
  struct Node {
    Node *left, *right, *prt;
    T key;
    int height, size;

    Node(T x) {
      left = right = prt = nullptr;
      height = 1;
      key = x;
      size = 1;
    }

    inline int factor() const {
      int lv = (this->left ? this->left->height : 0);
      int rv = (this->right ? this->right->height : 0);
      return (rv - lv);
    }

    inline int update_height() {
      return this->height = max(
        (this->left ? this->left->height : 0),
        (this->right ? this->right->height : 0)
      ) + 1;
    }

    inline bool is_left(Node *node) const {
      return left == node;
    }

    inline void assign(Node *node) {
      this->key = node->key;
    }

    inline Node* rotate_left() {
      Node *r = this->right, *m = r->left, *p = this->prt;
      if(r->prt = p) {
        if(p->left == this) p->left = r;
        else p->right = r;
      }
      if(this->right = m) m->prt = this;
      r->left = this; this->prt = r;

      int sz = this->size;
      this->size += (m ? m->size : 0) - r->size;
      r->size = sz;

      this->update_height();
      r->update_height();
      return r;
    }

    inline Node* rotate_right() {
      Node *l = this->left, *m = l->right, *p = this->prt;
      if(l->prt = p) {
        if(p->left == this) p->left = l;
        else p->right = l;
      }
      if(this->left = m) m->prt = this;
      l->right = this; this->prt = l;

      int sz = this->size;
      this->size += (m ? m->size : 0) - l->size;
      l->size = sz;

      this->update_height();
      l->update_height();
      return l;
    }

    inline Node* rotate_double_right() {
      Node *l = this->left, *p = this->prt,
           *m = l->right, *ml = m->left, *mr = m->right;
      if((m->prt = p)) {
        if(p->left == this) p->left = m;
        else p->right = m;
      }
      if((l->right = ml)) ml->prt = l;
      if((this->left = mr)) mr->prt = this;
      m->left = l; l->prt = m;
      m->right = this; this->prt = m;

      int sz = this->size;
      this->size += (mr ? mr->size : 0) - l->size;
      l->size += (ml ? ml->size : 0) - m->size;
      m->size = sz;

      this->update_height();
      l->update_height();
      m->update_height();

      return m;
    }

    inline Node* rotate_double_left() {
      Node *r = this->right, *p = this->prt,
           *m = r->left, *ml = m->left, *mr = m->right;
      if(m->prt = p) {
        if(p->left == this) p->left = m;
        else p->right = m;
      }
      if(this->right = ml) ml->prt = this;
      if(r->left = mr) mr->prt = r;
      m->left = this; this->prt = m;
      m->right = r; r->prt = m;

      int sz = this->size;
      this->size += (ml ? ml->size : 0) - r->size;
      r->size += (mr ? mr->size : 0) - m->size;
      m->size = sz;

      this->update_height();
      r->update_height();
      m->update_height();

      return m;
    }
  };

  Node *root;

  inline Node* find_node(Node *node, T x) {
    if(node == nullptr) return nullptr;
    while(node->key != x) {
      if(x < node->key) {
        if(!node->left) break;
        node = node->left;
      } else {
        if(!node->right) break;
        node = node->right;
      }
    }
    return node;
  }

  inline void remove_node(Node *node) {
    T x = node->key;
    Node *prt = node->prt;

    if(!node->left || !node->right) {
      Node *n_node = (node->left ? node->left : node->right);
      if(prt) {
        if(x < prt->key) {
          prt->left = n_node;
        } else {
          prt->right = n_node;
        }
      }
      if((node = n_node)) node->prt = prt;
    } else {
      Node *c_node = find_node(node->right, x), *n_node = c_node->right;
      Node *c_prt = c_node->prt;
      if(node->right == c_node) {
        if((node->right = n_node)) n_node->prt = c_prt;
      } else {
        if((c_prt->left = n_node)) n_node->prt = c_prt;
      }
      node->assign(c_node);
      node = n_node; prt = c_prt;
    }

    while(prt) {
      --prt->size;
      prt->update_height();
      if(prt->is_left(node)) {
        if(prt->factor() == 2) {
          Node *sib = prt->right;
          if(sib->factor() < 0) {
            node = prt->rotate_double_left();
          } else {
            node = prt->rotate_left();
          }
        } else {
          if(prt->factor() == 1) break;
          node = prt;
        }
        prt = node->prt;
      } else {
        if(prt->factor() == -2) {
          Node *sib = prt->left;
          if(sib->factor() > 0) {
            node = prt->rotate_double_right();
          } else {
            node = prt->rotate_right();
          }
        } else {
          if(prt->factor() == -1) break;
          node = prt;
        }
        prt = node->prt;
      }
    }
    if(prt) {
      node = prt; prt = prt->prt;
      while(prt) {
        --prt->size;
        prt->update_height();
        node = prt; prt = node->prt;
      }
    }
    this->root = node;
  }

public:
  AVLTree() {
    root = nullptr;
  }

  inline bool find(T x) {
    if(!this->root) {
      return false;
    }

    Node *node = find_node(this->root, x);
    return (node->key == x);
  }

  inline T at(int k) {
    if(!this->root) {
      return 0;
    }
    // assert(0 <= k < size);

    Node *node = this->root;
    ++k;
    while(1) {
      int l_size = (node->left ? node->left->size : 0) + 1;
      if(l_size == k) break;

      if(k < l_size) {
        node = node->left;
      } else {
        node = node->right;
        k -= l_size;
      }
    }
    return node->key;
  }

  inline bool insert(T x) {
    if(!this->root) {
      this->root = new Node(x);
      return true;
    }

    Node *node = find_node(this->root, x);
    if(node->key == x) {
      return false;
    }

    Node *new_node = new Node(x);
    new_node->prt = node;
    if(x < node->key) {
      node->left = new_node;
    } else {
      node->right = new_node;
    }
    node = new_node;

    while(node->prt) {
      Node *prt = node->prt;
      ++prt->size;
      prt->update_height();
      if(prt->is_left(node)) {
        if(prt->factor() == -2) {
          if(node->factor() > 0) {
            node = prt->rotate_double_right();
          } else {
            node = prt->rotate_right();
          }
        } else {
          if(prt->factor() >= 0) break;
          node = prt;
        }
      } else {
        if(prt->factor() == 2) {
          if(node->factor() < 0) {
            node = prt->rotate_double_left();
          } else {
            node = prt->rotate_left();
          }
        } else {
          if(prt->factor() <= 0) break;
          node = prt;
        }
      }
    }
    if(node->prt) {
      node = node->prt;
      Node *prt = node->prt;
      while(prt) {
        ++prt->size;
        prt->update_height();
        node = prt; prt = node->prt;
      }
    }
    this->root = node;
    return true;
  }

  inline bool remove(T x) {
    if(!this->root) {
      return false;
    }

    Node *node = find_node(this->root, x);
    if(node->key != x) {
      return false;
    }

    remove_node(node);
    return true;
  }

  int size() {
    return (this->root ? this->root->size : 0);
  }
};

void solve(){
    ll n,k,q;
    cin >> n >> k >> q;
    vl a(n);
    rep(i,n)cin >> a[i];
    AVLTree<ll> tree;
    rep(i,n){
        tree.insert(a[i]);
    }
    rep(i,q){
        ll op,x,y;
        cin >> op;
        if(op==1){
            cin >> x;
            tree.insert(x);
        }
        else if(op==2){
            cin >> y;
            x=tree.at(k-1);
            tree.remove(x);
            tree.insert(x+y);
        }
        else{
            cout << tree.at(k-1) << endl;
        }
    }
}


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll t = 1;
    // cin >> t;
    while (t--) solve();
}