結果
問題 |
No.789 範囲の合計
|
ユーザー |
|
提出日時 | 2025-07-03 23:00:12 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 916 ms / 1,000 ms |
コード長 | 1,031 bytes |
コンパイル時間 | 413 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 47,828 KB |
最終ジャッジ日時 | 2025-07-03 23:00:25 |
合計ジャッジ時間 | 9,785 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
N = int(input()) class BinaryIndexedTree: def __init__(self, n): self.size = n self.bit = [0] * (n + 1) def sum(self, i): s = 0 while i > 0: s += self.bit[i] i -= i & -i return s def add(self, i, x): i += 1 while i <= self.size: self.bit[i] += x i += i & -i def subtract(self, i, x): i += 1 while i <= self.size: self.bit[i] -= x i += i & -i q = [0] * N for i in range(N): q[i] = list(map(int, input().split())) s = set() for i in range(N): if q[i][0] == 0: s.add(q[i][1]) else: s.add(q[i][1]) s.add(q[i][2]) s = sorted(s) l = len(s) d = dict() for i in range(len(s)): d[s[i]] = i del s s = BinaryIndexedTree(l) ans = 0 for i in range(N): if q[i][0] == 0: x = d[q[i][1]] s.add(x, q[i][2]) else: l = d[q[i][1]] r = d[q[i][2]] ans += s.sum(r+1) - s.sum(l) print(ans)