Submission #17968851


Source Code Expand

Copy
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

@njit((i8, i8, i8[:, :], i8[:, :]), cache=True)
def main(H, W, AB, CD):
    G = np.zeros((H, W), np.int64)
    for i in range(len(AB)):
        a, b = AB[i]
        G[a - 1, b - 1] = 1
    for i in range(len(CD)):
        c, d = CD[i]
        G[c - 1, d - 1] = -1
    res = np.zeros((H, W), np.bool_)  # 光ったマス
    for _ in range(4):
        res, G = res.T[::-1], G.T[::-1]
        # 下方向に解く
        A = np.zeros_like(res)
        H, W = A.shape
        for h in range(H):
            if h >= 1:
                A[h] |= A[h - 1]
            A[h][G[h] == 1] = 1
            A[h][G[h] == -1] = 0
        res |= A
    return np.sum(res)

H, W, N, M = map(int, readline().split())
nums = from_read()
AB = nums[:N + N].reshape(N, 2)
CD = nums[N + N:].reshape(M, 2)

print(main(H, W, AB, CD))

Submission Info

Submission Time
Task E - Akari
User maspy
Language Python (3.8.2)
Score 500
Code Size 1240 Byte
Status AC
Exec Time 610 ms
Memory 139968 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 20
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All handmade_00.txt, max_random_00.txt, max_random_01.txt, max_random_02.txt, max_random_03.txt, max_random_04.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, sample_01.txt, sample_02.txt, sample_03.txt, surrounded_00.txt
Case Name Status Exec Time Memory
handmade_00.txt AC 491 ms 105700 KB
max_random_00.txt AC 586 ms 137428 KB
max_random_01.txt AC 581 ms 138124 KB
max_random_02.txt AC 587 ms 138072 KB
max_random_03.txt AC 580 ms 138104 KB
max_random_04.txt AC 586 ms 137380 KB
random_00.txt AC 610 ms 139612 KB
random_01.txt AC 597 ms 139968 KB
random_02.txt AC 468 ms 106872 KB
random_03.txt AC 471 ms 106216 KB
random_04.txt AC 532 ms 124568 KB
random_05.txt AC 527 ms 124808 KB
random_06.txt AC 521 ms 122284 KB
random_07.txt AC 553 ms 131128 KB
random_08.txt AC 477 ms 108440 KB
random_09.txt AC 541 ms 127376 KB
sample_01.txt AC 469 ms 106232 KB
sample_02.txt AC 469 ms 106548 KB
sample_03.txt AC 471 ms 106552 KB
surrounded_00.txt AC 590 ms 138132 KB