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

Submission #16874853

Source Code Expand

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

@njit((numba.types.optional(i8), ) * 2, cache=True)
def seg_f(x, y):
if x is None:
return y
if y is None:
return x
return min(x, y)

@njit((i8[:], i8[:]), cache=True)
def build(seg, raw_data):
N = len(seg) // 2
seg[N:] = raw_data
for i in range(N - 1, 0, -1):
seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])

@njit((i8[:], i8, i8), cache=True)
def set_val(seg, i, x):
N = len(seg) // 2
i += N
seg[i] = x
while i > 1:
i >>= 1
seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])

@njit((i8[:], i8, i8), cache=True)
def fold(seg, l, r):
vl = vr = None
N = len(seg) // 2
l, r = l + N, r + N
while l < r:
if l & 1:
vl = seg_f(vl, seg[l])
l += 1
if r & 1:
r -= 1
vr = seg_f(seg[r], vr)
l, r = l >> 1, r >> 1
return seg_f(vl, vr)

@njit((i8, i8[:]), cache=True)
def main(N, TX):
dp1 = np.full(N, N - 2, np.int64)
dp2 = np.full(N, N - 2, np.int64)
seg1 = np.full(N + N, N - 2, np.int64)
seg2 = np.full(N + N, N - 2, np.int64)
filled1 = np.zeros(N, np.int64)
filled2 = np.zeros(N, np.int64)

ans = 0
for i in range(0, len(TX), 2):
t, x = TX[i:i + 2]
x -= 2
if t == 1 and filled1[x]:
continue
if t == 2 and filled2[x]:
continue
if t == 1:
n = fold(seg2, x, N)
ans += n
if n:
dp1[n - 1] = min(dp1[n - 1], x)
set_val(seg1, n - 1, dp1[n - 1])
elif t == 2:
n = fold(seg1, x, N)
ans += n
if n:
dp2[n - 1] = min(dp2[n - 1], x)
set_val(seg2, n - 1, dp2[n - 1])
return (N - 2) * (N - 2) - ans

print(main(N, TX))```

#### Submission Info

Submission Time 2020-09-19 21:42:14+0900 F - Simplified Reversi maspy Python (3.8.2) 600 2154 Byte AC 593 ms 124936 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
 AC × 3
 AC × 21
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.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, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt 504 ms 106432 KB
hand_02.txt 494 ms 106560 KB
hand_03.txt 483 ms 106344 KB
random_01.txt 593 ms 124236 KB
random_02.txt 504 ms 119036 KB
random_03.txt 585 ms 123104 KB
random_04.txt 529 ms 116828 KB
random_05.txt 581 ms 124936 KB
random_06.txt 561 ms 121176 KB
random_07.txt 589 ms 124184 KB
random_08.txt 507 ms 114412 KB
random_09.txt 586 ms 124192 KB
random_10.txt 481 ms 107092 KB
random_11.txt 554 ms 122692 KB
random_12.txt 539 ms 117520 KB
random_13.txt 573 ms 124088 KB
random_14.txt 561 ms 123620 KB
random_15.txt 561 ms 123412 KB
sample_01.txt 484 ms 106336 KB
sample_02.txt 497 ms 119316 KB
sample_03.txt 501 ms 118052 KB