結果

問題 No.3411 Range Clamp Sum
コンテスト
ユーザー AwashAmityOak
提出日時 2025-12-17 01:54:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,472 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 477 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 271,980 KB
最終ジャッジ日時 2025-12-17 23:36:28
合計ジャッジ時間 23,362 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# TLE想定のナイーブ

import sys

N, Q = map(int, sys.stdin.readline().split())
(*A,) = [(int(a), i) for i, a in enumerate(sys.stdin.readline().split())]

rN = int((N**0.5) + 0.5)
rQ = int((Q**0.5) + 0.5)

queries = [[] for _ in range((Q + rQ - 1) // rQ)]
for q in range(Q):
    t, *query = map(int, sys.stdin.readline().split())
    assert t == 1 or t == 2

    if t == 1:
        x, y = query
        x -= 1

        queries[q // rQ].append((t, x, y, -1, -1))
    else:
        l, r, a, b = query
        l -= 1

        queries[q // rQ].append((t, l, r, a, b))

answer = []
for block in queries:
    ans = [0] * len(block)

    B = A[:]
    B.sort()
    events = [(float("inf"), -1, -1, -1, -1)] * (Q * 2)
    e = 0
    for q in range(len(block)):
        t, l, r, a, b = block[q]
        if t == 1:
            continue

        events[e] = a, l, r, q, 0
        events[e + 1] = b, l, r, q, 1
        e += 2
    events.sort()

    j = 0
    sum0, sum1 = [0] * N, [0] * N
    bsum0, bsum1 = [0] * ((N + rN - 1) // rN), [0] * ((N + rN - 1) // rN)
    for x, l, r, q, t in events:
        if x == float("inf"):
            break

        while j < N and B[j][0] < x:
            a, i = B[j]
            sum0[i] += 1
            sum1[i] += a
            bsum0[i // rN] += 1
            bsum1[i // rN] += a
            j += 1

        s0, s1 = 0, 0
        bl, br = (l + rN - 1) // rN, r // rN
        if bl > br:
            s0 += sum(sum0[l:r])
            s1 += sum(sum1[l:r])
        else:
            s0 += sum(bsum0[bl:br])
            s0 += sum(sum0[l : bl * rN])
            s0 += sum(sum0[br * rN : r])
            s1 += sum(bsum1[bl:br])
            s1 += sum(sum1[l : bl * rN])
            s1 += sum(sum1[br * rN : r])

        if t == 0:
            ans[q] -= s1
            ans[q] += s0 * x
        else:
            ans[q] += s1
            ans[q] += (r - l - s0) * x

    update_history = {}
    for q in range(len(block)):
        t, l, r, a, b = block[q]
        if t == 1:
            update_history[l] = r
        elif a > b:
            answer.append(a * (r - l))
            continue
        else:
            for i, x in update_history.items():
                if l <= i < r:
                    ans[q] -= max(a, min(b, A[i][0]))
                    ans[q] += max(a, min(b, x))
            answer.append(ans[q])

    for i, x in update_history.items():
        A[i] = (x, i)

sys.stdout.write("\n".join(map(str, answer)))
sys.stdout.write("\n")
0