問題概要
問題ページ
-
-
E - Akari
問題ページへ移動する
問題文
\(H\) 行 \(W\) 列のマス目があります。このマス目の \(i\) 行目 \(j\) 列目のマスをマス \((i, j)\) と呼ぶことにします。
このマス目の上には \(N\) 個の電球と \(M\) 個のブロックが置かれていて、\(i\) 個目の電球はマス \((A_i, B_i)\) に、\(i\) 個目のブロックはマス \((C_i, D_i)\) に置かれています。一つのマスにある電球とブロックは合計で高々一つです。
全ての電球は、ブロックが置かれているマスに到達するまで届く光を上下左右の \(4\) 方向に放ちます。電球が置かれているマス自身にも光が届くものとします。
マス目上のブロックの置かれていないマスのうち電球の光が届くものの数を求めてください。
制約
- \(1 \le H, W \le 1500\)
- \(1 \le N \le 5 \times 10^5\)
- \(1 \le M \le 10^5\)
- \(1 \le A_i \le H\)
- \(1 \le B_i \le W\)
- \(1 \le C_i \le H\)
- \(1 \le D_i \le W\)
- \((A_i, B_i) \neq (A_j, B_j)\ \ (i \neq j)\)
- \((C_i, D_i) \neq (C_j, D_j)\ \ (i \neq j)\)
- \((A_i, B_i) \neq (C_j, D_j)\)
- 入力はすべて整数
問題の考察
ACコード
import sys
def solve():
readline = sys.stdin.buffer.readline
mod = 10 ** 9 + 7
h, w, n, m = list(map(int, readline().split()))
ab = [list(map(int, readline().split())) for _ in range(n)]
hw = [[[False] * w for _ in range(h)] for _ in range(3)]
for i in range(m):
c, d = list(map(int, readline().split()))
hw[0][c-1][d-1] = True
for a, b in ab:
a, b = a - 1, b - 1
if not hw[1][a][b]:
for i in range(a, h):
if hw[0][i][b] or hw[1][i][b]:
break
else:
hw[1][i][b] = True
for i in range(a - 1, -1, -1):
if hw[0][i][b] or hw[1][i][b]:
break
else:
hw[1][i][b] = True
if not hw[2][a][b]:
for i in range(b, w):
if hw[0][a][i] or hw[2][a][i]:
break
else:
hw[2][a][i] = True
for i in range(b - 1, -1, -1):
if hw[0][a][i] or hw[2][a][i]:
break
else:
hw[2][a][i] = True
cnt = 0
for i in range(h):
for j in range(w):
if hw[1][i][j] or hw[2][i][j]:
cnt += 1
print(cnt)
if __name__ == '__main__':
solve()