本番では、AtCoderとの連戦かつ深夜テンションでばぐばぐなコードを投げまくってしまい、終了2分前にようやくACを取れました・・・。
問題
https://codeforces.com/contest/1293/problem/C
問題概要
2行n列の通路がある。(1,1)から(2,n)まで移動したいのだが、一定時間毎に一つのセルで障害物が現れたり消えたりする。
開始からqターンまでのそれぞれで、通路が通過可能になっているかどうかを答えよ。
考察
通路の長さn、ターン数qともに10^5という制約なので、毎回すべてをチェックしていては間に合いません。
各列が通過可能になっているかどうかと、通過可能列がいくつあるかを記録しておき、障害物の出現や消失に合わせて、必要な範囲だけを書き換えることで計算量を減らすことができます。
障害物が現れた時は、
_x_ _x_
のパターンになっていると通過不可能であることはもちろんのこと
x__ _x_
や
__x _x_
のように、斜めに塞がっている場合も通過不可能になります。
なので、それまで通過可能であった列に関して、新たに現れた障害物によって上記のパターンになっていないかどうかを最大3列分確認していけばよいです。（もちろん、1列目やn列目に障害物が現れた場合に範囲外をチェックしてしまわないように注意します。） 各列の通過可能状態が変化した場合はそれを記録し、通過可能列の数も合わせて変更します。
障害物が消えた場合も考え方は上記と同様で、それまで通過不可能であった列に関して通過可能になったかどうかを3列分確認すればよいです。
極限状態で散らかったコード → Submission #69145369 - Codeforces
