トヨタシステムズプログラミングコンテスト2021 (AtCoder Beginner Contest 228) D - Linear Probing (400)

コンテスト中の考察

埋まっている区間を持っておく

今更新したい地点がどの区間にも入っていなかったら今の地点を更新して、区間を追加

今の更新したい地点から区間が始まっている場合、

端まで届いてない区間なら区間の最後の後ろを更新

届いている場合、最も手前の区間について処理する

1より大きいなら0を更新して、区間を追加

1なら0を更新して区間を手前に延ばす

0なら最後に追加

そうでない場合手前の区間に追加

後ろの区間とくっつく場合はくっつける

WAまたはRE

解説の解法1

開いている区間を持っておく

今の地点が区間の中なら前後の二つの区間に分割する

そうでない場合、後ろの開いている区間の最初を更新する

後ろが最後まで埋まっていた場合は事前に0の地点を見ていることにしておく

解説の解法2

それぞれの地点で次に開いている地点を持っておく

値を更新するときは次の開いている地点となっている地点を次に見る

開いてない場合はその次の開いている地点を見る

帰り際に最終的に更新された地点の次の地点の次に開いている地点で途中で見た点全ての次に開いている地点を更新する