結果
問題 | No.2065 Sum of Min |
ユーザー |
![]() |
提出日時 | 2022-09-02 21:40:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 564 ms / 2,000 ms |
コード長 | 1,605 bytes |
コンパイル時間 | 506 ms |
コンパイル使用メモリ | 82,116 KB |
実行使用メモリ | 106,780 KB |
最終ジャッジ日時 | 2024-11-16 02:48:32 |
合計ジャッジ時間 | 12,114 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
mod = 998244353def main():import sysinput = sys.stdin.buffer.readlineclass Bit:def __init__(self, n):self.size = nself.tree = [0] * (n + 1)def sum(self, i):if i == 0:return 0s = 0while i > 0:s += self.tree[i]i -= i & -ireturn sdef add(self, i, x):while i <= self.size:self.tree[i] += xi += i & -idef lower_bound(self, w):if w <= 0:return 0x = 0k = 1 << (self.size.bit_length() - 1)while k:if x + k <= self.size and self.tree[x + k] < w:w -= self.tree[x + k]x += kk >>= 1return x + 1N, Q = map(int, input().split())A = list(map(int, input().split()))query = []for q in range(Q):l, r, x = map(int, input().split())query.append((x, l, r, q))for i, a in enumerate(A):query.append((a, i+1))query.sort(key=lambda z: z[0])bit_val = Bit(N)bit_num = Bit(N)ans = [0] * Qfor line in query:if len(line) == 2:a, i = linebit_num.add(i, 1)bit_val.add(i, a)else:x, l, r, q = linenum = bit_num.sum(r) - bit_num.sum(l-1)ans[q] = bit_val.sum(r) - bit_val.sum(l - 1) + x * (r - l + 1 - num)print(*ans, sep="\n")if __name__ == '__main__':main()