公式

D - Chargers 解説 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;
}

投稿日時:
最終更新: