公式

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

投稿日時:
最終更新: