ABC 179 F - Simplified Reversi

$n \times n$ のグリッドの行または列を選択し，すでに塗られているマスに到達するまでマスを塗りつぶすという操作を $q$ 回行い，最終的に塗られていないマスの数を求める．( $n,q \leq 2 \times 10 ^ {5}$ )

atcoder.jp

解説

グリッドは $0$ 行目，$0$ 列目から数える．$R _ {i}$ を $i$ 行目で塗られているマスのうち最も左にある列番号，$C _ {j}$ を $j$ 列目で塗られているマスのうち最も上にある行番号として，各操作ごとに $R, C$ を更新しながら塗られたマスの個数を数えればよい．ただし，1回の更新で最大 $O(n)$ の計算量が必要になってしまうので，工夫したい．

具体的には，$R _ 0, C _ 0$ をそれぞれ $h, w$ として，選択された行または列から $h$ 行目または $w$ 列目までだけを更新するようにすれば，$1$ つの行または列は操作全体を通して $1$ 回しか更新されないので，全体での計算量が $O(n + q)$ に抑えられる．

例えば，$n = 9$ の場合を考えてみる．最初 $h = 9, w = 9$ である．
$7$ 列目が選択されたので，$C _ {7}, C _ {8}$ を $h = 9$ に更新し，$w$ を $7$ に更新する．このとき塗られたマスは $C _ {7} = 9$ 個である．

$6$ 行目が選択されたので，$R _ {6}, R _ {7}, R _ {8}$ を $w = 7$ に更新し，$h$ を $6$ に更新する．このとき塗られたマスは $R _ {6} = 7$ 個である．

$3$ 列目が選択されたので，$C _ {3}, C _ {4}, C _ {5}, C _ {6}$ を $h = 6$ に更新し，$w$ を $3$ に更新する．このとき塗られたマスは $C _ {3} = 6$ 個である．

$5$ 列目が選択されたが，$5 > w = 3$ なので更新しない．このとき塗られたマスは $C _ {5} = 6$ 個である．

以上の操作では，合計 $9 + 7 + 6 + 6 = 28$ 個のマスが塗られたので，残りは $9 \times 9 - 28 = 53$ 個である．

実装

Submission #16957278 - AtCoder Beginner Contest 179

n, q = map(int, input().split())
n -= 2
R, C = [None] * n, [None] * n
h, w = n, n
a = n**2
for _ in range(q):
    t, x = map(int, input().split())
    x -= 2
    if t == 1:
        for i in range(x, h):
            R[i] = w
        h = min(h, x)
        a -= R[x]
    if t == 2:
        for j in range(x, w):
            C[j] = h
        w = min(w, x)
        a -= C[x]
print(a)