Submission #14813105


Source Code Expand

Copy
import sys
import numpy as np
import numba

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

i4 = numba.int32

def get_input():
    D = int(readline())
    C = np.array(readline().split(), np.int32)
    S = np.array([readline().split() for _ in range(D)], np.int32)
    T = np.array([readline() for _ in range(D)], np.int32)
    T -= 1
    Q = int(readline())
    query = np.array(read().split(), np.int32).reshape(-1, 2)
    query -= 1
    return D, C, S, T, query

@numba.njit((i4, i4[:], i4[:, :], i4[:]), cache=True)
def first_computation(D, C, S, T):
    x = 0
    last = np.zeros((26, D), np.int32)
    for d in range(D):
        if d:
            last[:, d] = last[:, d - 1]
        i = T[d]
        x += S[d, i]
        last[i, d] = d + 1
        for i in range(26):
            x -= C[i] * (d + 1 - last[i, d])
    return last, x

@numba.njit((i4, i4[:], i4[:, :], i4[:], i4[:, :], i4, i4), cache=True)
def difference_update(D, C, S, T, last_day, d, q):
    p = T[d]
    T[d] = q
    x = S[d, q] - S[d, p]

    i = np.searchsorted(last_day[p], d + 1)
    d_p = last_day[p, i - 1] if i >= 1 else 0
    coef = 0
    for k in range(d, D):
        if last_day[p, k] == d + 1:
            # k 日目に入るスコアの変更
            coef += d_p - d - 1
            last_day[p, k] = d_p
        else:
            break
    x += coef * C[p]

    coef = 0
    for k in range(d, D):
        if last_day[q, k] < d + 1:
            coef += (d + 1 - last_day[q, k])
            last_day[q, k] = d + 1
        else:
            break
    x += coef * C[q]
    return x

@numba.njit((i4, i4[:], i4[:, :], i4[:], i4[:, :], i4[:, :], i4), cache=True)
def main(D, C, S, T, query, last_day, score):
    for i in range(len(query)):
        d, q = query[i]
        score += difference_update(D, C, S, T, last_day, d, q)
        print(score)

D, C, S, T, query = get_input()
last_day, score = first_computation(D, C, S, T)

main(D,C,S,T,query,last_day,score)

Submission Info

Submission Time
Task C - Incremental Scoring
User maspy
Language Python (3.8.2)
Score 1
Code Size 2081 Byte
Status
Exec Time 618 ms
Memory 117836 KB

Judge Result

Set Name Score / Max Score Test Cases
test_ALL 1 / 1 test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt
Case Name Status Exec Time Memory
test_00.txt 559 ms 106776 KB
test_01.txt 543 ms 106800 KB
test_02.txt 536 ms 106904 KB
test_03.txt 538 ms 107476 KB
test_04.txt 618 ms 117836 KB