モノグサプログラミングコンテスト2022 (AtCoder Beginner Contest 249) F - Ignore Operations (500)
1の操作が行われる場合、それ以前の2の操作は意味が無いことが分かる
操作を後ろから見ていく
2の操作の場合
$ y \lt 0なら優先度付きキューに入れる
キューに$ k個より多く要素があったら一番大きな値を取り出して和に加算
そうでないなら和に加算
1の操作の場合
和に$ yを加えて最大値なら更新
kが0なら終了
これ以前の操作の影響を受けるにはこの要素を無視するしかないのでkを1減らす
キューで要素が溢れてしまうなら1個取り出す
各操作で優先度付きキューを操作するので$ \mathcal{O}(N \log K)
問題: https://atcoder.jp/contests/abc249/tasks/abc249_f
提出: https://atcoder.jp/contests/abc249/submissions/31195824
#モノグサプログラミングコンテスト2022 #ABC249 #500pt #F #モノグサプログラミングコンテスト #ABC #AtCoder
#優先度付きキュー #逆向き