結果

問題 No.3298 K-th Slime
ユーザー Kanato Sugano
提出日時 2025-10-05 14:57:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 189 ms / 2,000 ms
コード長 2,857 bytes
コンパイル時間 4,515 ms
コンパイル使用メモリ 281,312 KB
実行使用メモリ 13,064 KB
最終ジャッジ日時 2025-10-05 14:58:01
合計ジャッジ時間 7,221 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <algorithm>
#include <atcoder/all>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ranges>
using namespace atcoder;

/* alias */
using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vs = vector<string>;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

/* define short */
#define pb push_back
#define mp make_pair
#define all(obj) (obj).begin(), (obj).end()
#define YESNO(bool)        \
  if (bool) {              \
    cout << "YES" << endl; \
  } else {                 \
    cout << "NO" << endl;  \
  }
#define yesno(bool)        \
  if (bool) {              \
    cout << "yes" << endl; \
  } else {                 \
    cout << "no" << endl;  \
  }
#define YesNo(bool)        \
  if (bool) {              \
    cout << "Yes" << endl; \
  } else {                 \
    cout << "No" << endl;  \
  }

/* REP macro */
#define rep(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define reps(i, a, n) for (ll i = (a); i <= (ll)(n); ++i)

template <typename T>
inline bool chmax(T& a, const T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

// 座標を表す構造体
struct Point {
  int y, x;

  // コンストラクタを追加
  Point(int y_ = 0, int x_ = 0) : y(y_), x(x_) {}

  // <
  bool operator<(const Point& other) const {
    if (y != other.y)
      return y < other.y;
    return x < other.x;
  }

  // == 一致確認
  bool operator==(const Point& other) const {
    return y == other.y && x == other.x;
  }
};

/*statement*/
bool flag = true;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int n, k, q;
  cin >> n >> k >> q;
  vi a;
  // multiset<int> slimes;
  // 重複を許す ordered multiset using (value, unique_id) as key
  // tree<key,null_type,less<key>,rb_tree_tag,tree_order_statistics_node_update> : ordered_set
  tree<pair<ll, int>, null_type, less<pair<ll, int>>, rb_tree_tag,
       tree_order_statistics_node_update>
      slimes;  // ordered multiset
  int uid = 0;
  rep(i, 0, n) {
    int input;
    cin >> input;
    a.pb(input);
    slimes.insert({input, uid++});
  }

  rep(i, 0, q) {
    int query;
    ll x;
    cin >> query;
    if (query == 1) {
      cin >> x;
      slimes.insert({x, uid++});
    } else {
      auto iter = slimes.find_by_order(k - 1);  // 0-index
      ll found = iter->first;
      if (query == 2) {
        cin >> x;
        slimes.erase(iter);
        slimes.insert({found + x, uid++});
      } else if (query == 3) {
        cout << found << endl;
      }
    }
  }
}
0