Official
D - Chargers Editorial
by
D - Chargers Editorial
by
sheyasutaka
時刻 \(t_0\) に残量 \(w_0\) で挿入したバッテリーについて,時刻 \(t\) における残量は \(w = \min(w_0 + (t - t_0),\ V)\) です.これは,\(u_0 := w_0 - t_0\) とおいて \(w = \min(t + u_0,\ V)\) と式変形できます.
時刻 \(t\) を固定したとき,\(\min(t + u_0,\ V)\) は \(u_0\) に対して広義単調増加です.また,ある時点で残量が等しい \(2\) バッテリーは,それ以降の任意の時刻でも残量が等しいことから,残量が等しいバッテリーたちの内からは \(u_0\) が大きいほうを優先して選ぶとしてよいです.
このとき,タイプ \(2\) のクエリでは \(u_0\) が大きいほうのバッテリーを貪欲に選んで排出します.
以上より,「\(u_0\) の値を追加」「\(u_0\) の最大値を取得・削除」の \(2\) 通りの処理を行えばよく,これは優先度付きキューによって実装できます.時間計算量は \(O(Q \log Q)\) となり,十分高速です.
実装例 (C++)
#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
using std::pair;
#include <map>
using std::map;
using std::max;
using std::min;
#include <queue>
using std::priority_queue;
using std::greater;
#ifdef DEBUG
const int debug = 1;
#else
const int debug = 0;
#endif
using ll = int64_t;
using P = pair<ll, ll>;
const ll FOD = 998244353;
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#include <atcoder/convolution>
using atcoder::convolution;
ll q, v;
inline void output (const ll x) {
cout << x << "\n";
}
void solve() {
priority_queue<ll, vector<ll> > que;
for (ll qi = 0; qi < q; qi++) {
ll type;
cin >> type;
if (type == 1) {
// type 1 (insert)
ll t, w;
cin >> t >> w;
que.push(w - t);
} else {
// type 2 (pop)
ll t;
cin >> t;
if (que.empty()) {
cout << "-1" << "\n";
} else {
ll w0 = que.top();
que.pop();
ll ans = min(w0 + t, v);
cout << ans << "\n";
}
}
}
return;
}
int main (void) {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
cin >> q >> v;
solve();
return 0;
}
