結果

問題 No.789 範囲の合計
コンテスト
ユーザー Akijin_007
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0