結果

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

ソースコード

diff #
raw source code 

import sys

N, Q = map(int, sys.stdin.readline().split())
(*A,) = [(int(a) << 17) + 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 << 17) + x << 17) + y << 17 * 2)
    else:
        l, r, a, b = query
        l -= 1

        queries[q // rQ].append(((((t << 17) + l << 17) + r << 17) + a << 17) + b)

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

    B = A[:]
    B.sort()
    events = []
    for q in range(len(block)):
        t = block[q]

        b = t & (1 << 17) - 1
        t >>= 17
        a = t & (1 << 17) - 1
        t >>= 17
        r = t & (1 << 17) - 1
        t >>= 17
        l = t & (1 << 17) - 1
        t >>= 17

        if t == 1:
            continue

        events.append(((((a << 17) + l << 17) + r << 17) + q << 1) + 0)
        events.append(((((b << 17) + l << 17) + r << 17) + q << 1) + 1)
    events.sort()

    j = 0
    sum0, sum1 = [0] * N, [0] * N
    bsum0, bsum1 = [0] * ((N + rN - 1) // rN), [0] * ((N + rN - 1) // rN)
    for e in range(len(events)):
        x = events[e]

        t = x & 1
        x >>= 1
        q = x & (1 << 17) - 1
        x >>= 17
        r = x & (1 << 17) - 1
        x >>= 17
        l = x & (1 << 17) - 1
        x >>= 17

        while j < N and (B[j] >> 17) < x:
            a, i = B[j] >> 17, B[j] & (1 << 17) - 1
            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 = block[q]

        b = t & (1 << 17) - 1
        t >>= 17
        a = t & (1 << 17) - 1
        t >>= 17
        r = t & (1 << 17) - 1
        t >>= 17
        l = t & (1 << 17) - 1
        t >>= 17

        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] >> 17))
                    ans[q] += max(a, min(b, x))
            answer.append(ans[q])

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

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