Querying Multiset
問題
D – Querying Multiset
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…
記録
- 2021/3/14 発想できず。加えるときの \(x – sum\) が思いつかず。
解法
priority_queue
で管理する。
コード例
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using P = pair<int, int>; #define rep(i, n) for(int i = 0; i < (n); ++i) // using mint = modint998244353; // using mint = modint1000000007; // const int mod = 1000000007; // const ll INF = 1LL << 60; // const int INF = 1001001001; int main() { int Q; cin >> Q; priority_queue<ll, vector<ll>, greater<ll>> pq; ll sum = 0; while(0 < Q) { ll P; cin >> P; if(P == 1) { ll x; cin >> x; pq.push(x - sum); } else if(P == 2) { ll x; cin >> x; sum += x; } else { ll v = pq.top(); pq.pop(); cout << v + sum << endl; } Q--; } return 0; }