ABC解説 Edit

【pythonでABC182を解説】E - Akari

問題概要

問題ページ

E - Akari
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()

-ABC解説, Edit
-