ABC471 D - Chargers
充電器
考え方
バッテリーが様々なタイミングで差し込まれる。
これを愚直にいちいち処理すると大変。
ところが、時刻 $t$ に残量 $w$ で差し込まれたというのを次のように言い換えれば簡単になる。
仮に、時刻 $0$ から残量 $w-t$ のバッテリーが挿されていたとしよう。
このバッテリーには、時刻 $t$ に残量 $w$ になっているはず。
つまり、時刻 $0$ から残量 $w-t$ のバッテリーがあったことに今気づいたということにしてもよい。
すると、「時刻 $0$ 時点で残量いくつだったか」を priority_queue で管理するだけの話になる。
クエリ $2$ が来た時には、初期残量に $t$ を加えてから $V$ 以上なら $V$ に丸める処理をすればよい。
計算量は $O(Q\log Q)$ である。
入力例1での動作
入力を受け取る。
q: 7
v: 100
1 15 60
1 25 80
2 30
1 45 0
2 60
2 70
2 80バッテリーを追加するときは、時刻 $0$ 時点での残量とみなした $w-t$ を管理する。
値が大きいものから取り出せるようにしておく。
各クエリは次のように処理される。
| クエリ | 処理 | 管理している値 | このクエリの答え |
|---|---|---|---|
1 15 60 |
$60-15=45$ を追加 | $45$ | |
1 25 80 |
$80-25=55$ を追加 | $55,45$ | |
2 30 |
$\min(100,55+30)=85$ のバッテリーを排出 | $45$ | $85$ |
1 45 0 |
$0-45=-45$ を追加 | $45,-45$ | |
2 60 |
$\min(100,45+60)=100$ のバッテリーを排出 | $-45$ | $100$ |
2 70 |
$\min(100,-45+70)=25$ のバッテリーを排出 | 空 | $25$ |
2 80 |
バッテリーがない | 空 | $-1$ |
タイプ $2$ の各クエリの答えは、順に $85,100,25,-1$ である。
注意点
特になし。
別解
特になし。