結果

問題 No.789 範囲の合計
ユーザー Fuyuru
提出日時 2024-02-22 00:13:11
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,265 bytes
コンパイル時間 239 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 163,104 KB
最終ジャッジ日時 2024-09-29 04:22:43
合計ジャッジ時間 5,465 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 2 MLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
class BIT:
    def __init__(self,N,default=0):
        self.s = (N-1).bit_length()
        self.N = 1<<self.s
        self.root = [None, None, 0] #[left-child, right-child, value]
        self.default = default
    def add(self,i,x):
        i += 1
        node = self.root
        tmp = self.N
        for j in range(self.s,-1,-1):
            if i == tmp:
                node[2] += x
                return
            elif i < tmp:
                node[2] += x
                if not node[0]:
                    node[0] = [None, None, self.default]
                tmp -= 1<<(j-1)
                node = node[0]
            else:
                if not node[1]:
                    node[1] = [None, None, self.default]
                tmp += 1<<(j-1)
                node = node[1]
    def fold_(self,r):
        res = 0
        node = self.root
        tmp = self.N
        for j in range(self.s,-1,-1):
            if r == tmp:
                res += node[2]
                return res
            elif r < tmp:
                if not node[0]:
                    return res
                tmp -= 1<<(j-1)
                node = node[0]
            else:
                res += node[2]
                if not node[1]:
                    return res
                tmp += 1<<(j-1)
                node = node[1]
    def fold(self,l,r):
        if l == 0:
            return self.fold_(r)
        else:
            return self.fold_(r)-self.fold_(l-1)
    def all_prod(self):
        return self.root[2]
    '''
    セグ木上にぶたんは未実装
    def max_right_(self,x):
        i = self.N
        if self.data[i] <= x:
            return self.N
        tmp = 0
        for j in range(self.s-1,-1,-1):
            if tmp+self.data[i] <= x:
                tmp += self.data[i]
                i += 1<<j
            else:
                i -= 1<<j
        if tmp+self.data[i] <= x:
            return i
        else:
            return i-1
    def max_right(self,l,x):
        return self.max_right_(self.fold(0,l)+x)
    '''


N = int(input())
bit = BIT(10**9+1)
ans = 0
for q in range(N):
    op,x,y = map(int,input().split())
    if op:
        ans += bit.fold(x,y+1)
    else:
        bit.add(x,y)
print(ans)
0