競技プログラミング用 知識集積所
ABC451C - Understory
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
- 特になし
考え方
木の追加と削除の仕方を考える。
追加は、順番は特に考えずに追加できればよい。
削除は、少し考える必要がある。
任意の場所から削除する方法だと毎回のチェック数が多く、大量に植えた後にちょっとだけ切り倒すクエリを連打されたときにTLEしてしまう。
そこで削除クエリは高さが低い順に調べられるようにしておきたい。
特に、次を見る必要があるのは最も低い木を削除したときだけなので、結局は常に最も低い木を見ることと削除することができればそれで十分。
追加は、順番は特に考えずに追加できればよい。
削除は、少し考える必要がある。
任意の場所から削除する方法だと毎回のチェック数が多く、大量に植えた後にちょっとだけ切り倒すクエリを連打されたときにTLEしてしまう。
そこで削除クエリは高さが低い順に調べられるようにしておきたい。
特に、次を見る必要があるのは最も低い木を削除したときだけなので、結局は常に最も低い木を見ることと削除することができればそれで十分。
ということで、priority_queue※が最適。
あとは問題の通りにシミュレーションするだけ。
あとは問題の通りにシミュレーションするだけ。
