結果

問題 No.789 範囲の合計
ユーザー FuyuruFuyuru
提出日時 2024-02-16 17:53:28
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,340 bytes
コンパイル時間 430 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 260,676 KB
最終ジャッジ日時 2024-09-28 19:20:13
合計ジャッジ時間 9,963 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
54,640 KB
testcase_01 AC 41 ms
53,936 KB
testcase_02 MLE -
testcase_03 AC 175 ms
76,996 KB
testcase_04 MLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 AC 171 ms
77,012 KB
testcase_08 MLE -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 MLE -
testcase_12 MLE -
testcase_13 WA -
testcase_14 AC 40 ms
55,056 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
import sys
input = sys.stdin.readline
#print = sys.stdout.write
class SegTree:
    def __init__(self,N,op,identity):
        self.op = op
        self.identity = identity
        self.N = N
        self.data = defaultdict(lambda: identity)
    def __getitem__(self,key):
        key += self.N
        return self.data[key]
    def build(self,A):
        for i in range(self.N):
            self.data[self.N+i] = A[i]
        for i in range(self.N-1,0,-1):
            self.data[i] = self.op(self.data[i<<1|0],self.data[i<<1|1])
    def set_value(self,x,val):
        x += self.N
        self.data[x] = val
        while x > 1:
            x >>= 1
            self.data[x] = self.op(self.data[x<<1|0],self.data[x<<1|1])
    def fold(self,l,r):
        l,r = l+self.N,r+self.N
        lv,rv = self.identity,self.identity
        while l < r:
            if l&1:
                lv = self.op(lv,self.data[l])
                l += 1
            if r&1:
                r -= 1
                rv = self.op(self.data[r],rv)
            l,r = l>>1,r>>1
        return self.op(lv,rv)


seg = SegTree(1000000000,lambda x,y:x+y,0)
Q = int(input())
ans = 0
for _ in range(Q):
    op,x,y = map(int,input().split())
    if op == 0:
        seg.set_value(x,seg[x]+y)
    else:
        ans += seg.fold(x,y+1)
print(ans)
0