Submission #13359130


Source Code Expand

Copy
import sys
import numpy as np

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

INF = 10**9 + 1

def precompute(N, M, data):
    data = data.reshape(-1, 3)
    A, B, C = data[:N].T
    D, E, F = data[N:].T
    X = np.unique(np.concatenate([A, B, D, [0, -INF, INF]]))
    Y = np.unique(np.concatenate([C, E, F, [0, -INF, INF]]))
    A = np.searchsorted(X, A)
    B = np.searchsorted(X, B)
    D = np.searchsorted(X, D)
    C = np.searchsorted(Y, C)
    E = np.searchsorted(Y, E)
    F = np.searchsorted(Y, F)
    return A, B, C, D, E, F, X, Y

def solve(A, B, C, D, E, F, X, Y):
    H, W = len(X), len(Y)
    N = H * W
    DX = X[1:] - X[:-1]
    DY = Y[1:] - Y[:-1]

    def set_ng(A, B, C, D, E, F, H, W):
        ng = np.zeros((H * W, 4), np.bool_)

        for i in range(len(A)):
            for x in range(A[i], B[i]):
                v = x * W + C[i]
                ng[v][1] = 1
                ng[v - 1][0] = 1

        for i in range(len(D)):
            for y in range(E[i], F[i]):
                v = D[i] * W + y
                ng[v][3] = 1
                ng[v - W][2] = 1
        return ng

    ng = set_ng(A, B, C, D, E, F, H, W)
    x0, y0 = np.searchsorted(X, 0), np.searchsorted(Y, 0)
    v0 = x0 * W + y0
    visited = np.zeros(N, np.bool_)
    visited[v0] = 1
    stack = np.empty(N, np.int32)
    p = 0
    ret = 0

    def area(x):
        x, y = divmod(x, W)
        return DX[x] * DY[y]

    def push(x):
        nonlocal p, ret
        stack[p] = x
        visited[x] = 1
        ret += area(x)
        p += 1

    def pop():
        nonlocal p
        p -= 1
        return stack[p]

    push(v0)
    move = (1, -1, W, -W)
    while p:
        v = pop()
        for i in range(4):
            if ng[v][i]:
                continue
            w = v + move[i]
            if visited[w]:
                continue
            x, y = divmod(w, W)
            if x == 0 or x == H - 1 or y == 0 or y == W - 1:
                return 0
            push(w)
    return ret

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    signature = '(i8[::1],i8[::1],i8[::1],i8[::1],i8[::1],i8[::1],i8[::1],i8[::1])'
    cc.export('solve', signature)(solve)
    cc.compile()

if sys.argv[-1] == 'ONLINE_JUDGE':
    cc_export()
    exit()

from my_module import solve

N, M = map(int, readline().split())
data = np.int64(read().split())

x = solve(*precompute(N, M, data))
if x == 0:
    print('INF')
else:
    print(x)

Submission Info

Submission Time
Task F - . (Single Dot)
User maspy
Language Python (3.8.2)
Score 600
Code Size 2614 Byte
Status
Exec Time 357 ms
Memory 86220 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
Subtask1 600 / 600 sample_01.txt, sample_02.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt, sub1_29.txt, sub1_30.txt, sub1_31.txt, sub1_32.txt, sub1_33.txt, sub1_34.txt, sub1_35.txt, sub1_36.txt, sub1_37.txt, sub1_38.txt, sub1_39.txt, sub1_40.txt, sub1_41.txt, sub1_42.txt, sub1_43.txt, sub1_44.txt, sub1_45.txt, sub1_46.txt, sub1_47.txt, sub1_48.txt, sub1_49.txt, sub1_50.txt, sub1_51.txt, sub1_52.txt, sub1_53.txt, sub1_54.txt, sub1_55.txt, sub1_56.txt, sub1_57.txt, sub1_58.txt, sub1_59.txt, sub1_60.txt, sub1_61.txt, sub1_62.txt, sub1_63.txt, sub1_64.txt, sub1_65.txt, sub1_66.txt, sub1_67.txt, sub1_68.txt, sub1_69.txt, sub1_70.txt, sub1_71.txt, sub1_72.txt, sub1_73.txt, sub1_74.txt, sub1_75.txt, sub1_76.txt, sub1_77.txt, sub1_78.txt, sub1_79.txt, sub1_80.txt, sub1_81.txt, sub1_82.txt, sub1_83.txt, sub1_84.txt, sub1_85.txt, sub1_86.txt, sub1_87.txt, sub1_88.txt, sub1_89.txt, sub1_90.txt, sub1_91.txt, sub1_92.txt, sub1_93.txt, sub1_94.txt
Case Name Status Exec Time Memory
sample_01.txt 100 ms 27272 KB
sample_02.txt 98 ms 27240 KB
sub1_01.txt 110 ms 40956 KB
sub1_02.txt 107 ms 36328 KB
sub1_03.txt 101 ms 32448 KB
sub1_04.txt 101 ms 29260 KB
sub1_05.txt 123 ms 54444 KB
sub1_06.txt 105 ms 36060 KB
sub1_07.txt 104 ms 36196 KB
sub1_08.txt 106 ms 34396 KB
sub1_09.txt 103 ms 34396 KB
sub1_10.txt 130 ms 60976 KB
sub1_11.txt 97 ms 27328 KB
sub1_12.txt 97 ms 27220 KB
sub1_13.txt 96 ms 27248 KB
sub1_14.txt 102 ms 27236 KB
sub1_15.txt 97 ms 26996 KB
sub1_16.txt 99 ms 27244 KB
sub1_17.txt 101 ms 31988 KB
sub1_18.txt 111 ms 32328 KB
sub1_19.txt 113 ms 32600 KB
sub1_20.txt 105 ms 32604 KB
sub1_21.txt 102 ms 31764 KB
sub1_22.txt 114 ms 31992 KB
sub1_23.txt 107 ms 32264 KB
sub1_24.txt 111 ms 32236 KB
sub1_25.txt 107 ms 32128 KB
sub1_26.txt 116 ms 32312 KB
sub1_27.txt 106 ms 31712 KB
sub1_28.txt 110 ms 31972 KB
sub1_29.txt 103 ms 32084 KB
sub1_30.txt 108 ms 31988 KB
sub1_31.txt 105 ms 32164 KB
sub1_32.txt 109 ms 32028 KB
sub1_33.txt 107 ms 32236 KB
sub1_34.txt 108 ms 31912 KB
sub1_35.txt 111 ms 32328 KB
sub1_36.txt 114 ms 32100 KB
sub1_37.txt 114 ms 32292 KB
sub1_38.txt 106 ms 27192 KB
sub1_39.txt 101 ms 27152 KB
sub1_40.txt 112 ms 32364 KB
sub1_41.txt 103 ms 27224 KB
sub1_42.txt 101 ms 27260 KB
sub1_43.txt 102 ms 27380 KB
sub1_44.txt 101 ms 27408 KB
sub1_45.txt 102 ms 27408 KB
sub1_46.txt 104 ms 27292 KB
sub1_47.txt 103 ms 28844 KB
sub1_48.txt 105 ms 28928 KB
sub1_49.txt 101 ms 29120 KB
sub1_50.txt 103 ms 28908 KB
sub1_51.txt 101 ms 28928 KB
sub1_52.txt 103 ms 28748 KB
sub1_53.txt 101 ms 28732 KB
sub1_54.txt 105 ms 28508 KB
sub1_55.txt 229 ms 71320 KB
sub1_56.txt 214 ms 71552 KB
sub1_57.txt 163 ms 72076 KB
sub1_58.txt 207 ms 71284 KB
sub1_59.txt 208 ms 69372 KB
sub1_60.txt 141 ms 70384 KB
sub1_61.txt 139 ms 41932 KB
sub1_62.txt 209 ms 65556 KB
sub1_63.txt 99 ms 27408 KB
sub1_64.txt 121 ms 53816 KB
sub1_65.txt 104 ms 27660 KB
sub1_66.txt 108 ms 30072 KB
sub1_67.txt 102 ms 27420 KB
sub1_68.txt 102 ms 28208 KB
sub1_69.txt 102 ms 28404 KB
sub1_70.txt 102 ms 28280 KB
sub1_71.txt 104 ms 27300 KB
sub1_72.txt 106 ms 26880 KB
sub1_73.txt 100 ms 27180 KB
sub1_74.txt 127 ms 45636 KB
sub1_75.txt 107 ms 30616 KB
sub1_76.txt 151 ms 71316 KB
sub1_77.txt 100 ms 27308 KB
sub1_78.txt 99 ms 27360 KB
sub1_79.txt 102 ms 27700 KB
sub1_80.txt 107 ms 27496 KB
sub1_81.txt 101 ms 27424 KB
sub1_82.txt 100 ms 27464 KB
sub1_83.txt 102 ms 27248 KB
sub1_84.txt 98 ms 27428 KB
sub1_85.txt 101 ms 27568 KB
sub1_86.txt 99 ms 27260 KB
sub1_87.txt 95 ms 27232 KB
sub1_88.txt 98 ms 27252 KB
sub1_89.txt 300 ms 86148 KB
sub1_90.txt 304 ms 86220 KB
sub1_91.txt 303 ms 86060 KB
sub1_92.txt 304 ms 86096 KB
sub1_93.txt 357 ms 85336 KB
sub1_94.txt 96 ms 27424 KB