結果

問題 No.789 範囲の合計
コンテスト
ユーザー Akijin_007
提出日時 2025-07-03 22:58:39
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,031 bytes
コンパイル時間 351 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 147,456 KB
最終ジャッジ日時 2025-07-03 22:58:45
合計ジャッジ時間 3,821 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 MLE * 7
権限があれば一括ダウンロードができます

ソースコード

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