結果

問題 No.3298 K-th Slime
コンテスト
ユーザー a01sa01to
提出日時 2025-10-11 00:41:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 126 ms / 2,000 ms
コード長 1,347 bytes
コンパイル時間 3,242 ms
コンパイル使用メモリ 283,580 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2025-10-11 00:41:54
合計ジャッジ時間 5,942 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, k, q;
  cin >> n >> k >> q;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  multiset<ll> lt, gt;
  rep(i, n) {
    if (lt.size() < k) {
      lt.insert(a[i]);
    }
    else {
      assert(lt.size() == k);
      ll x = *lt.rbegin();
      if (x <= a[i]) {
        gt.insert(a[i]);
      }
      else {
        lt.erase(prev(lt.end()));
        lt.insert(a[i]);
        gt.insert(x);
      }
    }
  }
  while (q--) {
    // cerr << format("{} {}\n", lt, gt);
    int t;
    cin >> t;
    assert(lt.size() == k);
    if (t == 1) {
      ll x;
      cin >> x;
      ll y = *lt.rbegin();
      if (y <= x) {
        gt.insert(x);
      }
      else {
        lt.erase(prev(lt.end()));
        lt.insert(x);
        gt.insert(y);
      }
    }
    if (t == 2) {
      ll x;
      cin >> x;
      ll y = *lt.rbegin();
      lt.erase(prev(lt.end()));
      y += x;
      ll z = gt.empty() ? 1e18 : *gt.begin();
      if (y <= z) {
        lt.insert(y);
      }
      else {
        gt.erase(gt.begin());
        lt.insert(z);
        gt.insert(y);
      }
    }
    if (t == 3) {
      cout << *lt.rbegin() << '\n';
    }
  }
  return 0;
}
0