D - Chargers Editorial by en_translator
For the battery plugged at time \(t_0\) with charge level \(w_0\), the charge level at time \(t\) is \(w = \min(w_0 + (t - t_0),\ V)\). By defining \(u_0 := w_0 - t_0\), this equals \(w = \min(t + u_0,\ V)\).
For a fixed time \(t\), the value \(\min(t + u_0,\ V)\) monotonically increases with respect to \(\min(t + u_0,\ V)\). Also, two batteries with the same charge level at some point will permanently have the same change level onwards, so we may assume that, among the battery with the same charge level, that with larger \(u_0\) is prioritized.
Under this assumption, a type-\(2\) query always unplugs the battery with the largest \(u_0\).
Hence, it suffices to process two kinds of operations: inserting \(u_0\), and retrieving and removing the maximum \(u_0\). Both can be implemented using a priority queue. The time complexity is \(O(Q \log Q)\), which is fast enough.
Sample code (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;
}