結果

問題 No.2065 Sum of Min
ユーザー ntudantuda
提出日時 2022-09-03 15:00:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,269 ms / 2,000 ms
コード長 1,211 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 148,112 KB
最終ジャッジ日時 2024-04-28 13:08:23
合計ジャッジ時間 20,943 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
52,736 KB
testcase_01 AC 41 ms
52,608 KB
testcase_02 AC 42 ms
52,608 KB
testcase_03 AC 44 ms
52,992 KB
testcase_04 AC 499 ms
140,672 KB
testcase_05 AC 433 ms
138,576 KB
testcase_06 AC 1,085 ms
117,568 KB
testcase_07 AC 289 ms
102,588 KB
testcase_08 AC 1,014 ms
123,084 KB
testcase_09 AC 1,161 ms
147,316 KB
testcase_10 AC 505 ms
142,352 KB
testcase_11 AC 498 ms
142,356 KB
testcase_12 AC 1,226 ms
148,112 KB
testcase_13 AC 1,242 ms
147,860 KB
testcase_14 AC 1,217 ms
147,272 KB
testcase_15 AC 1,244 ms
147,348 KB
testcase_16 AC 1,233 ms
148,096 KB
testcase_17 AC 1,269 ms
147,336 KB
testcase_18 AC 1,239 ms
148,108 KB
testcase_19 AC 1,228 ms
147,320 KB
testcase_20 AC 1,217 ms
147,844 KB
testcase_21 AC 1,239 ms
147,960 KB
権限があれば一括ダウンロードができます

ソースコード

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