結果
問題 | No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに |
ユーザー |
👑 |
提出日時 | 2022-10-16 16:12:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,410 ms / 6,000 ms |
コード長 | 1,615 bytes |
コンパイル時間 | 501 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 207,984 KB |
最終ジャッジ日時 | 2024-06-27 11:24:47 |
合計ジャッジ時間 | 75,927 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
class Bit:def __init__(self, n):self.size = nself.n0 = 1 << (n.bit_length() - 1)self.tree = [0] * (n + 1)def range_sum(self, l, r):return self.sum(r - 1) - self.sum(l - 1)def sum(self, i):i += 1s = 0while i > 0:s += self.tree[i]i -= i & -ireturn sdef get(self, i):return self.sum(i) - self.sum(i - 1)def add(self, i, x):i += 1while i <= self.size:self.tree[i] += xi += i & -idef lower_bound(self, x):pos = 0plus = self.n0while plus > 0:if pos + plus <= self.size and self.tree[pos + plus] < x:x -= self.tree[pos + plus]pos += plusplus //= 2return posn = int(input())bit_a = Bit(n)bit_b = Bit(n)event = []for i in range(n):a, t = map(int, input().split())bit_b.add(i, a)event.append((0, t, a, i))event.append((1, t + a, a, i))Q = int(input())for i in range(Q):d, l, r = map(int, input().split())event.append((2, d, l, r, i))ans = [0] * Qevent.sort(key=lambda x:x[1])for query in event:if query[0] == 0:d, a, i = query[1:]bit_a.add(i, -1)bit_b.add(i, d - 1)elif query[0] == 1:d, a, i = query[1:]bit_a.add(i, 1)bit_b.add(i, -d + 1)else:d, l, r, i = query[1:]a = bit_a.range_sum(l - 1, r)b = bit_b.range_sum(l - 1, r)ans[i] = a * d + bprint(*ans, sep="\n")