結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using lint = long long;

template<typename T>
struct compress {
  int n, idx;
  vector<T> vec;
  vector<T> com;
  compress(const vector<T> &vec_, int idx_ = 0) {
    n = (int)vec_.size(), idx = idx_;
    vec.resize(n), com.resize(n, idx);
    vec = vec_;
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    for (int i = 0; i < n; i++) com[i] += (int)distance(vec.begin(), lower_bound(vec.begin(), vec.end(), vec_[i]));
  }
  vector<T> get() {
    return com;
  }
  T get(T x) {
    return (int)distance(vec.begin(), lower_bound(vec.begin(), vec.end(), x));
  }
  T rev(int x) {
    return vec[x];
  }
  int operator[](int x) {
    return com[x];
  }
};

int op(int a, int b) {
    return a+b;
}

int e() {
    return (int)(0);
}

int k;

bool f(int x) {
  if (x < k) return true;
  else return false;
}

int main() {
  int n, q;
  cin >> n >> k >> q;
  vector<int> a(n);
  vector<int> vec(n);
  for (int i = 0; i < n; i++) cin >> a[i], vec[i] = a[i];
  vector<pair<int, int>> query(q);
  for (int i = 0; i < q; i++) {
    int t, x=0;
    cin >> t;
    if (t != 3) cin >> x, vec.push_back(x);
    query[i] = {t, x};
  }
  compress<int> com(vec);
  segtree<int, op, e> seg(n+q);
  for (int i = 0; i < n; i++) seg.set(com.get(a[i]), seg.get(com.get(a[i]))+1);
  for (int i = 0; i < q; i++) {
    int t = query[i].first, x = query[i].second;
    if (t == 1) {
      seg.set(com.get(x), seg.get(com.get(x))+1);
    }
    if (t == 3) {
      int idx = seg.max_right<f>(0);
      // idx-1がk-1番目とならない最大
      // idxがk-1番目となることが保証
      cout << com.rev(idx) << endl;
    }
    if (t == 2) {
      int idx = seg.max_right<f>(0);
      seg.set(idx, seg.get(idx)-1);
      int _n = com.get(com.rev(idx)+x);
      seg.set(_n, seg.get(_n)+1);
    }
  }

}
0