結果
問題 |
No.3298 K-th Slime
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }