Submission #13344551


Source Code Expand

Copy
import sys
import numpy as np
from numba import njit

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

INF = 10**9 + 1

N, M = map(int, readline().split())
data = np.array(read().split(), np.int64)
A = data[::3]
B = data[1::3]
C = data[2::3]

D = A[N:]
E = B[N:]
F = C[N:]
A = A[:N]
B = B[:N]
C = C[:N]

X = np.unique(np.concatenate([A, B, D, [0, -INF, INF]]))
Y = np.unique(np.concatenate([C, E, F, [0, -INF, INF]]))
DX = X[1:] - X[:-1]
DY = Y[1:] - Y[:-1]

A = np.searchsorted(X, A)
B = np.searchsorted(X, B)
C = np.searchsorted(Y, C)
D = np.searchsorted(X, D)
E = np.searchsorted(Y, E)
F = np.searchsorted(Y, F)

H, W = len(X), len(Y)
N = H * W

@njit
def set_ng(A, B, C, D, E, F):
    p = 0
    head = np.full(N, -1, np.int32)
    ng = np.empty(4 * N, np.int32)
    nxt = np.empty(4 * N, np.int32)

    def add(v, w):
        nonlocal p
        nxt[p] = head[v]
        head[v] = p
        ng[p] = w
        p += 1

    for i in range(len(A)):
        a, b, c = A[i], B[i], C[i]
        for x in range(a, b):
            v = x * W + c
            add(v, v - 1)
            add(v - 1, v)
    for i in range(len(D)):
        d, e, f = D[i], E[i], F[i]
        for y in range(e, f):
            v = d * W + y
            add(v, v - W)
            add(v - W, v)
    return head, ng[:p], nxt[:p]

head, ng, nxt = set_ng(A, B, C, D, E, F)

@njit
def next_w(head, ng, nxt, v):
    p = head[v]
    V = [v - W, v + W, v - 1, v + 1]
    while p != -1:
        V.remove(ng[p])
        p = nxt[p]
    return V

x0, y0 = np.searchsorted(X, 0), np.searchsorted(Y, 0)
v0 = x0 * W + y0

@njit
def solve():
    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)
    while p:
        v = pop()
        for w in next_w(head, ng, nxt, v):
            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

x = solve()
if x == 0:
    print('INF')
else:
    print(x)

Submission Info

Submission Time
Task F - . (Single Dot)
User maspy
Language Python (3.8.2)
Score 0
Code Size 2510 Byte
Status RE
Exec Time 2435 ms
Memory 227088 KB

Judge Result

Set Name Sample Subtask1
Score / Max Score 0 / 0 0 / 600
Status
AC × 2
AC × 94
RE × 2
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
Subtask1 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 AC 1322 ms 120448 KB
sample_02.txt AC 1233 ms 120924 KB
sub1_01.txt AC 1269 ms 140596 KB
sub1_02.txt AC 1257 ms 134436 KB
sub1_03.txt AC 1255 ms 128984 KB
sub1_04.txt AC 1369 ms 143084 KB
sub1_05.txt AC 1280 ms 160172 KB
sub1_06.txt AC 1247 ms 134808 KB
sub1_07.txt AC 1256 ms 137648 KB
sub1_08.txt AC 1277 ms 135364 KB
sub1_09.txt AC 1261 ms 133588 KB
sub1_10.txt AC 1315 ms 179444 KB
sub1_11.txt AC 1337 ms 131212 KB
sub1_12.txt AC 1246 ms 121660 KB
sub1_13.txt AC 1243 ms 121128 KB
sub1_14.txt AC 1237 ms 120416 KB
sub1_15.txt AC 1236 ms 121476 KB
sub1_16.txt AC 1223 ms 120620 KB
sub1_17.txt AC 1371 ms 143880 KB
sub1_18.txt AC 1422 ms 144820 KB
sub1_19.txt AC 1404 ms 144680 KB
sub1_20.txt AC 1365 ms 143228 KB
sub1_21.txt AC 1363 ms 141856 KB
sub1_22.txt AC 1376 ms 142360 KB
sub1_23.txt AC 1359 ms 144048 KB
sub1_24.txt AC 1389 ms 143816 KB
sub1_25.txt AC 1376 ms 143076 KB
sub1_26.txt AC 1404 ms 144772 KB
sub1_27.txt AC 1410 ms 147524 KB
sub1_28.txt AC 1403 ms 146452 KB
sub1_29.txt AC 1391 ms 146644 KB
sub1_30.txt AC 1404 ms 147116 KB
sub1_31.txt AC 1416 ms 145700 KB
sub1_32.txt AC 1372 ms 143500 KB
sub1_33.txt AC 1377 ms 143528 KB
sub1_34.txt AC 1390 ms 145112 KB
sub1_35.txt RE 1398 ms 145672 KB
sub1_36.txt AC 1394 ms 143632 KB
sub1_37.txt AC 1401 ms 141864 KB
sub1_38.txt AC 1307 ms 131376 KB
sub1_39.txt AC 1258 ms 124748 KB
sub1_40.txt AC 1393 ms 142984 KB
sub1_41.txt AC 1294 ms 130296 KB
sub1_42.txt AC 1241 ms 121264 KB
sub1_43.txt AC 1233 ms 120352 KB
sub1_44.txt AC 1242 ms 120636 KB
sub1_45.txt AC 1237 ms 120524 KB
sub1_46.txt AC 1232 ms 120564 KB
sub1_47.txt AC 1310 ms 132104 KB
sub1_48.txt AC 1315 ms 130020 KB
sub1_49.txt AC 1302 ms 132016 KB
sub1_50.txt AC 1300 ms 130084 KB
sub1_51.txt AC 1295 ms 131116 KB
sub1_52.txt AC 1290 ms 129852 KB
sub1_53.txt AC 1309 ms 132540 KB
sub1_54.txt AC 1310 ms 131748 KB
sub1_55.txt AC 1699 ms 171416 KB
sub1_56.txt RE 1528 ms 172184 KB
sub1_57.txt AC 1276 ms 169592 KB
sub1_58.txt AC 1624 ms 171564 KB
sub1_59.txt AC 1624 ms 169584 KB
sub1_60.txt AC 1294 ms 169136 KB
sub1_61.txt AC 1389 ms 138004 KB
sub1_62.txt AC 1604 ms 165476 KB
sub1_63.txt AC 1254 ms 124524 KB
sub1_64.txt AC 1271 ms 150732 KB
sub1_65.txt AC 1382 ms 145152 KB
sub1_66.txt AC 1346 ms 138440 KB
sub1_67.txt AC 1282 ms 125272 KB
sub1_68.txt AC 1394 ms 145792 KB
sub1_69.txt AC 1386 ms 149216 KB
sub1_70.txt AC 1409 ms 152028 KB
sub1_71.txt AC 1249 ms 120380 KB
sub1_72.txt AC 1229 ms 120056 KB
sub1_73.txt AC 1226 ms 120892 KB
sub1_74.txt AC 1284 ms 163468 KB
sub1_75.txt AC 1263 ms 129720 KB
sub1_76.txt AC 1336 ms 220568 KB
sub1_77.txt AC 1250 ms 121940 KB
sub1_78.txt AC 1249 ms 121444 KB
sub1_79.txt AC 1249 ms 122020 KB
sub1_80.txt AC 1247 ms 122032 KB
sub1_81.txt AC 1255 ms 122244 KB
sub1_82.txt AC 1255 ms 122620 KB
sub1_83.txt AC 1228 ms 120568 KB
sub1_84.txt AC 1251 ms 122184 KB
sub1_85.txt AC 1255 ms 123064 KB
sub1_86.txt AC 1232 ms 120416 KB
sub1_87.txt AC 1230 ms 120408 KB
sub1_88.txt AC 1248 ms 120472 KB
sub1_89.txt AC 1910 ms 226920 KB
sub1_90.txt AC 1903 ms 227088 KB
sub1_91.txt AC 1901 ms 227076 KB
sub1_92.txt AC 1906 ms 226392 KB
sub1_93.txt AC 2435 ms 226500 KB
sub1_94.txt AC 1234 ms 120704 KB