結果

問題 No.3330 Many Point Chmax Range Sum
ユーザー kidodesu
提出日時 2025-10-31 17:54:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,092 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 82,896 KB
実行使用メモリ 266,544 KB
最終ジャッジ日時 2025-11-03 20:51:57
合計ジャッジ時間 50,535 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, k, q = map(int, input().split())
A = list(map(int, input().split()))
Ans = [None] * q

update = [None] * k
for i in range(k):
    p, x = map(int, input().split())
    update[i] = (p-1, x)

B_size = int(k ** 0.5)
B_cnt = k // B_size + 1

query = [[] for _ in range(B_cnt)]
etc = []
for i in range(q):
    l, r, d, u = map(int, input().split())
    l, d = l-1, d-1
    if r - l <= B_size:
        etc.append((l, r, d, u, i))
    else:
        query[l // B_size].append((l, r, d, u, i))

C_size = int(n ** 0.5)
C_cnt = n // C_size + 1
B = [0] * C_cnt
for i in range(n):
    B[i // C_size] += A[i]

for l, r, d, u, i in etc:
    S = []
    for p, x in update[l: r]:
        if A[p] < x and d <= p < u:
            S.append((p, A[p], p // C_size, B[p // C_size]))
            B[p // C_size] += x - A[p]
            A[p] = x
    now = d
    rep = 0
    while now < u:
        if not now % C_size and now + C_size <= u:
            rep += B[now // C_size]
            now += C_size
        else:
            rep += A[now]
            now += 1
    for p, x, p_, x_ in S[::-1]:
        A[p] = x
        B[p_] = x_
    Ans[i] = rep

A_ = A[:]
B_ = B[:]

for i in range(B_cnt):
    if not query[i]:
        continue
    A = A_[:]
    B = B_[:]
    query[i].sort(key = lambda x: x[1])
    l = r = B_size * (i+1)
    for nl, nr, d, u, i in query[i]:
        for p, x in update[r: nr]:
            if A[p] < x:
                B[p // C_size] += x - A[p]
                A[p] = x
        r = nr
        S = []
        for p, x in update[nl: l]:
            if A[p] < x and d <= p < u:
                S.append((p, A[p], p // C_size, B[p // C_size]))
                B[p // C_size] += x - A[p]
                A[p] = x
        now = d
        rep = 0
        while now < u:
            if not now % C_size and now + C_size <= u:
                rep += B[now // C_size]
                now += C_size
            else:
                rep += A[now]
                now += 1
        for p, x, p_, x_ in S[::-1]:
            A[p] = x
            B[p_] = x_
        Ans[i] = rep

for ans in Ans:
    print(ans)
0