Contest Duration: - (local time) (100 minutes) Back to Home

Submission #13389928

Source Code Expand

Copy
```import sys
import numpy as np

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([D, [0, -INF, INF]]))
Y = np.unique(np.concatenate([C, [0, -INF, INF]]))
A = np.searchsorted(X, A)
B = np.searchsorted(X, B, 'right') - 1
D = np.searchsorted(X, D)
C = np.searchsorted(Y, C)
E = np.searchsorted(Y, E)
F = np.searchsorted(Y, F, 'right') - 1
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

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

#### Submission Info

Submission Time 2020-05-19 08:13:51+0900 F - . (Single Dot) maspy Python (3.8.2) 600 2628 Byte AC 131 ms 32512 KB

#### Judge Result

Score / Max Score 0 / 0 600 / 600
Status
 AC × 2
 AC × 96
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 109 ms 27172 KB
sample_02.txt AC 104 ms 27124 KB
sub1_01.txt AC 109 ms 28852 KB
sub1_02.txt AC 103 ms 27984 KB
sub1_03.txt AC 105 ms 27688 KB
sub1_04.txt AC 107 ms 27348 KB
sub1_05.txt AC 111 ms 30020 KB
sub1_06.txt AC 103 ms 27664 KB
sub1_07.txt AC 107 ms 28012 KB
sub1_08.txt AC 105 ms 27388 KB
sub1_09.txt AC 102 ms 27732 KB
sub1_10.txt AC 108 ms 30980 KB
sub1_11.txt AC 109 ms 27500 KB
sub1_12.txt AC 102 ms 27260 KB
sub1_13.txt AC 102 ms 27212 KB
sub1_14.txt AC 104 ms 27200 KB
sub1_15.txt AC 103 ms 27444 KB
sub1_16.txt AC 102 ms 27168 KB
sub1_17.txt AC 105 ms 31952 KB
sub1_18.txt AC 118 ms 32200 KB
sub1_19.txt AC 114 ms 31944 KB
sub1_20.txt AC 110 ms 32256 KB
sub1_21.txt AC 106 ms 31740 KB
sub1_22.txt AC 113 ms 32140 KB
sub1_23.txt AC 108 ms 32188 KB
sub1_24.txt AC 113 ms 32512 KB
sub1_25.txt AC 107 ms 32132 KB
sub1_26.txt AC 117 ms 32332 KB
sub1_27.txt AC 106 ms 31116 KB
sub1_28.txt AC 106 ms 31364 KB
sub1_29.txt AC 112 ms 31480 KB
sub1_30.txt AC 105 ms 31484 KB
sub1_31.txt AC 108 ms 31396 KB
sub1_32.txt AC 107 ms 31368 KB
sub1_33.txt AC 106 ms 31696 KB
sub1_34.txt AC 106 ms 31712 KB
sub1_35.txt AC 115 ms 31584 KB
sub1_36.txt AC 106 ms 31720 KB
sub1_37.txt AC 117 ms 32284 KB
sub1_38.txt AC 101 ms 27544 KB
sub1_39.txt AC 103 ms 27376 KB
sub1_40.txt AC 117 ms 32508 KB
sub1_41.txt AC 100 ms 27340 KB
sub1_42.txt AC 101 ms 27168 KB
sub1_43.txt AC 100 ms 27112 KB
sub1_44.txt AC 105 ms 27268 KB
sub1_45.txt AC 102 ms 27200 KB
sub1_46.txt AC 107 ms 27176 KB
sub1_47.txt AC 100 ms 27524 KB
sub1_48.txt AC 104 ms 27368 KB
sub1_49.txt AC 105 ms 27576 KB
sub1_50.txt AC 102 ms 27360 KB
sub1_51.txt AC 102 ms 27472 KB
sub1_52.txt AC 99 ms 27652 KB
sub1_53.txt AC 104 ms 27496 KB
sub1_54.txt AC 101 ms 27400 KB
sub1_55.txt AC 116 ms 32148 KB
sub1_56.txt AC 115 ms 32408 KB
sub1_57.txt AC 114 ms 32408 KB
sub1_58.txt AC 113 ms 31888 KB
sub1_59.txt AC 113 ms 31852 KB
sub1_60.txt AC 108 ms 32068 KB
sub1_61.txt AC 106 ms 28464 KB
sub1_62.txt AC 117 ms 31636 KB
sub1_63.txt AC 101 ms 26844 KB
sub1_64.txt AC 107 ms 30236 KB
sub1_65.txt AC 103 ms 27268 KB
sub1_66.txt AC 113 ms 30140 KB
sub1_67.txt AC 101 ms 27044 KB
sub1_68.txt AC 103 ms 28020 KB
sub1_69.txt AC 105 ms 28192 KB
sub1_70.txt AC 105 ms 28252 KB
sub1_71.txt AC 103 ms 27328 KB
sub1_72.txt AC 100 ms 27268 KB
sub1_73.txt AC 107 ms 26872 KB
sub1_74.txt AC 106 ms 28812 KB
sub1_75.txt AC 104 ms 27188 KB
sub1_76.txt AC 114 ms 31932 KB
sub1_77.txt AC 101 ms 27404 KB
sub1_78.txt AC 103 ms 27344 KB
sub1_79.txt AC 101 ms 27068 KB
sub1_80.txt AC 104 ms 27344 KB
sub1_81.txt AC 104 ms 27040 KB
sub1_82.txt AC 100 ms 27560 KB
sub1_83.txt AC 100 ms 26852 KB
sub1_84.txt AC 107 ms 27532 KB
sub1_85.txt AC 103 ms 27564 KB
sub1_86.txt AC 104 ms 27440 KB
sub1_87.txt AC 100 ms 27436 KB
sub1_88.txt AC 100 ms 27204 KB
sub1_89.txt AC 126 ms 31676 KB
sub1_90.txt AC 130 ms 31936 KB
sub1_91.txt AC 129 ms 31948 KB
sub1_92.txt AC 125 ms 32136 KB
sub1_93.txt AC 131 ms 31900 KB
sub1_94.txt AC 106 ms 27324 KB