結果
問題 | No.2065 Sum of Min |
ユーザー |
![]() |
提出日時 | 2022-09-02 22:47:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,287 ms / 2,000 ms |
コード長 | 945 bytes |
コンパイル時間 | 344 ms |
コンパイル使用メモリ | 82,096 KB |
実行使用メモリ | 167,980 KB |
最終ジャッジ日時 | 2024-11-16 05:15:04 |
合計ジャッジ時間 | 23,047 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
class BIT:def __init__(self, n):self.n = n; self.k = [0]*(n+1)def a(self, i, x):while i <= self.n: self.k[i] += x; i += i&-idef s(self, i):t = 0while i > 0: t += self.k[i]; i -= i&-ireturn tdef r(self, l, r): return self.s(r)-self.s(l-1)n, q = map(int, input().split())a = list(map(int, input().split()))lrmpxi = []vxset = set(a)for i in range(q):l, r, x = map(int, input().split())lrmpxi.append((l-2, -1, x, i))lrmpxi.append((r-1, 1, x, i))vxset.add(x)vxtoi = {vx: i+1 for i, vx in enumerate(sorted(vxset))}bit_sum = BIT(n+q+1)bit_num = BIT(n+q+1)j = -1ans = [0]*qfor lr, mp, x, i in sorted(lrmpxi):while j < lr:j += 1v = a[j]bit_sum.a(vxtoi[v], v)bit_sum.a(n+q+1, -v)bit_num.a(1, 1)bit_num.a(vxtoi[v], -1)ans[i] += mp*(bit_sum.s(vxtoi[x])+x*bit_num.s(vxtoi[x]))print(*ans, sep="\n")