結果

問題 No.2065 Sum of Min
ユーザー ntudantuda
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,780 KB
testcase_01 AC 38 ms
53,852 KB
testcase_02 AC 40 ms
53,556 KB
testcase_03 AC 41 ms
54,468 KB
testcase_04 AC 465 ms
140,484 KB
testcase_05 AC 434 ms
138,496 KB
testcase_06 AC 1,080 ms
117,284 KB
testcase_07 AC 278 ms
102,764 KB
testcase_08 AC 1,021 ms
122,992 KB
testcase_09 AC 1,209 ms
147,596 KB
testcase_10 AC 515 ms
142,480 KB
testcase_11 AC 508 ms
142,736 KB
testcase_12 AC 1,256 ms
147,832 KB
testcase_13 AC 1,283 ms
147,784 KB
testcase_14 AC 1,257 ms
147,312 KB
testcase_15 AC 1,258 ms
147,464 KB
testcase_16 AC 1,262 ms
148,360 KB
testcase_17 AC 1,285 ms
147,580 KB
testcase_18 AC 1,276 ms
147,828 KB
testcase_19 AC 1,292 ms
147,320 KB
testcase_20 AC 1,273 ms
147,964 KB
testcase_21 AC 1,274 ms
148,028 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