D - Deforestation (nikkei2019_final_d) 🎍

Quiz

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_d

Submit

https://atcoder.jp/contests/nikkei2019-final/submissions/4334442

解法

• editorialの通り
• https://img.atcoder.jp/nikkei2019-final/editorial.pdf

注意点

• setから消していくとき、L〜Rの値がそれぞれsetにあるか判定すると、全体でO(N²)になってTLE
  • 例 https://atcoder.jp/contests/nikkei2019-final/submissions/4334349
• setでfindではなくlower_boundを使う
• setで消しつつiterator++すれば、iteratorの移動は全体でO(N)回で済む

学び

• setでのlower_bound, iterator++