提出 #16874853

---

ソースコード 拡げる

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

@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

N, Q = map(int, readline().split())
TX = np.array(read().split(), np.int64)

print(main(N, TX))

提出情報

ジャッジ結果