ABC 401-500/ABC426C - Upgrade Required - 競技プログラミング用 知識集積所

---

問題

ABC426C

必要知識

B以下レベルの内容は省略

• 特になし

考え方

愚直にやって簡単そうに見えるが、それでは計算量が多すぎてTLEする。

問題の性質上、同じバージョンのPCが大量にできるので、まとめて「このバージョンのPCが何台」というデータにしてしまうとよい。
そこで、小さい方を取り出すpriority_queue※の中に{バージョン,台数}というpair※を入れて扱うことにする。
すると、

• 「バージョンがX以下であるものは合計で何台あるか？」に対して高速に答える
• ついでに、それらの情報を削除する
• 「バージョンがYであるPCが（削除した合計台数）だけできた」という情報を追加する

の3つを高速にできる。

一見、最大N個のデータをQ回扱ってO(NQ)かかるように見える。
しかし、実は1回のクエリでM個分のデータを合計した場合、データ数がM-1小さくなっていくため、クエリからの取り出しは最大でもN+Q-1回である。
つまり計算量はO( (N+Q)log(N+Q) )であり、間に合う。

解答例

解答例

注意点

別解