Submission #20202419

---

Source Code Expand

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

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

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

@njit
def build(raw_data):
    shape = raw_data.shape
    N = len(raw_data)
    bit = np.zeros((N + 1, ) + shape[1:], np.int64)
    for i in range(1, N + 1):
        bit[i] += raw_data[i - 1]
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit
def get_sum(bit, i):
    """sum on [0, i)"""
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit
def add(bit, i, x=1):
    assert i >= 0
    i += 1
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit
def find_kth_element(bit, k):
    assert k > 0
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x

@njit((i8[:], i8[:, :]), cache=True)
def main(A, PD):
    A = A[::-1].copy()
    N = len(A)
    ans = 0
    for i in range(N):
        if (N - 1 - i) % 2 == 0:
            ans += A[i]

    # 係数

    dp = np.zeros(N, np.int64)
    dp[0] = A[0]
    for i in range(1, N):
        x = A[i]
        dp[i] = min(dp[i - 1], x)

    C = np.zeros(N, np.int64)
    for i in range(N - 1):
        if (N - i) % 2 == 0:
            C[i] = 1
        else:
            C[i] = -1
    ans += (dp * C).sum()
    print(ans)

    Ccum = np.append(0, np.cumsum(C))
    """
    累積 min の様子だけが問題。累積 min になる瞬間の座標の集合を管理する
    """
    X = np.zeros(N, np.int64)
    H = np.zeros(N, np.int64)
    X[0], H[0] = 1, A[0]
    h = A[0]
    for i in range(1, N):
        if h > A[i]:
            X[i] = 1
            h = A[i]
            H[i] = h
    X = np.append(X, 1)
    H = np.append(H, -1)
    bit = build(X)
    X_sum = X.sum()

    def coef(L, R):
        return Ccum[R] - Ccum[L]

    for q in range(len(PD)):
        i, d = PD[q]
        i = N - i
        A[i] -= d
        if (N - 1 - i) % 2 == 0:
            ans -= d
        k = get_sum(bit, i + 1)
        L = find_kth_element(bit, k)
        R = find_kth_element(bit, k + 1)
        if L == i:
            ans += coef(L, R) * (A[i] - H[i])
            H[i] = A[i]
        elif H[L] > A[i]:
            assert X[i] == 0
            ans -= coef(L, R) * H[L]
            ans += coef(L, i) * H[L]
            X[i] = 1
            H[i] = A[i]
            add(bit, i, 1)
            ans += coef(i, R) * H[i]
        if X[i] == 1:
            # 右の長方形を削るかどうか
            while True:
                k = get_sum(bit, i + 1)
                R = find_kth_element(bit, k + 1)
                assert i < R
                if H[i] > H[R]:
                    break
                RR = find_kth_element(bit, k + 2)
                ans += (H[i] - H[R]) * coef(R, RR)
                X[R] = 0
                H[R] = 0
                add(bit, R, -1)
        print(ans)

N = int(readline())
A = from_readline()
Q = int(readline())
PD = from_read().reshape(Q, 2)

main(A, PD)

Submission Info

Judge Result