結果

問題 No.2065 Sum of Min
ユーザー ntuda
提出日時 2022-09-03 15:00:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,292 ms / 2,000 ms
コード長 1,211 bytes
コンパイル時間 399 ms
コンパイル使用メモリ 82,068 KB
実行使用メモリ 148,360 KB
最終ジャッジ日時 2024-11-17 04:56:05
合計ジャッジ時間 21,785 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect_right, bisect_left

N, Q = map(int, input().split())
A = list(map(int, input().split()))
LRX = [list(map(int, input().split())) for _ in range(Q)]

L = []
for i, (l, r, x) in enumerate(LRX):
    if l > 1:
        L.append((l - 1, i, 0))
    L.append((r, i, 1))
L.sort()
L.append((10**10,))
B = sorted(list(set(A)))
NB = len(B)
D = dict(zip(B, range(1, NB + 1)))



class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

T = Bit(NB)
S = Bit(NB)
j = 0
nextlr = L[j][0]
ans = [0] * Q
for i in range(N):
    T.add(D[A[i]], 1)
    S.add(D[A[i]], A[i])
    while nextlr == i + 1:
        _, t, lr = L[j]
        x = LRX[t][2]
        ix = bisect_left(B, x)
        cnt = T.sum(ix)
        sum0 = S.sum(ix)
        if lr == 0:
            ans[t] -= sum0 + (i + 1 - cnt) * x
        else:
            ans[t] += sum0 + (i + 1 - cnt) * x
        j += 1
        nextlr = L[j][0]

for q in range(Q):
    print(ans[q])
0