Quiz
https://codeforces.com/contest/1132/problem/C
Submit
https://codeforces.com/contest/1132/submission/50862056
解法
- 除去する2人を全パターン試すとO(N3)となってしまう
- 除去する1人を固定する
- 残りq-1人で塗る。各箇所が何回塗られたかをカウントしておく
- その塗りのうち、塗りが1の箇所のみに注目
- 除去する2人目を決めたとき、範囲内＆塗り1の箇所のみペンキがはがれて0になる
- 塗り1だけを見た累積和を持っておけばいい
- 全体の計算量 O(N2)
感想
- コンテスト中に解けず
- 2000人/8000くらいが解けていたので解きたかった
- 理解はできたので今後に期待
学び
- ギリギリの部分だけに注目した累積和
