結果
問題 |
No.649 ここでちょっとQK!
|
ユーザー |
|
提出日時 | 2023-06-27 17:37:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 269 ms / 3,000 ms |
コード長 | 1,794 bytes |
コンパイル時間 | 729 ms |
コンパイル使用メモリ | 76,348 KB |
実行使用メモリ | 5,916 KB |
最終ジャッジ日時 | 2024-07-04 10:16:26 |
合計ジャッジ時間 | 6,664 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 32 |
ソースコード
#include <iostream> #include <queue> using namespace std; using ll = long long; using vll = vector<ll>; struct DynamicPriorityQueue{ priority_queue<ll> small;// small.top() は small の最大値 (K個になるようにする) priority_queue<ll, vector<ll>, greater<ll>> large; // large.top() は large の最小値 int K; void addElement(ll value) { if (small.size() < K) small.push(value); else { ll current_kth = small.top(); if (value < current_kth) { small.pop(); small.push(value); large.push(current_kth); } else { large.push(value); } } } ll getKthSmallest() { if (small.size() < K) { return -1; // K番目の値が存在しない場合は-1を返す } ll current_kth = small.top(); return current_kth; } void removeKthSmallest() { if (small.size() < K) return; // K番目の値が存在しない場合は何もしない ll current_kth = small.top(); small.pop(); if (!large.empty()) { long long next_kth = large.top(); large.pop(); small.push(next_kth); } } }; int main() { DynamicPriorityQueue dq; int Q, K; cin >> Q >> K; dq.K = K; vll ans; for (int i = 0; i < Q; ++i) { int T; cin >> T; if (T == 1) { ll V; cin >> V; dq.addElement(V); } else { ll kthSmallest = dq.getKthSmallest(); ans.push_back(kthSmallest); dq.removeKthSmallest(); } } for (int i = 0; i < ans.size(); ++i) { cout << ans[i] << endl; } return 0; }