結果

問題 No.789 範囲の合計
コンテスト
ユーザー るこーそー
提出日時 2025-03-14 09:14:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,716 bytes
コンパイル時間 439 ms
コンパイル使用メモリ 82,780 KB
実行使用メモリ 159,656 KB
最終ジャッジ日時 2025-03-14 09:14:42
合計ジャッジ時間 16,170 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 8 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegTree:
    class Node:
        def __init__(self,v):
            self.v=v
            self.l=self.r=None
    def __init__(self,op,e,v,r=1<<20):
        self.op=op
        self.e=e
        self.root=None
        if isinstance(v,list):
            self.l,self.r=0,len(v)
            self.root=self._build(v,0,len(v))
        else:
            self.l,self.r=0,v
    def _build(self,v,l,r):
        if r-l==1:
            return self.Node(v[l])
        m=(l+r)//2
        node=self.Node(self.e)
        node.l=self._build(v,l,m)
        node.r=self._build(v,m,r)
        node.v=self.op(node.l.v,node.r.v)
        return node
    def _set(self,p,x,node,l,r):
        if node is None:
            node=self.Node(self.e)
        if r-l==1:
            node.v=x
            return node
        m=(l+r)//2
        if p<m:
            node.l=self._set(p,x,node.l,l,m)
        else:
            node.r=self._set(p,x,node.r,m,r)
        node.v=self.op(node.l.v if node.l else e ,node.r.v if node.r else e)
        return node
    def _get(self,p,node,l,r):
        if node is None:
            return self.e
        if r-l==1:
            return node.v
        m=(l+r)//2
        if p<m:
            return self._get(p,node.l,l,m)
        else:
            return self._get(p,node.r,m,r)
    def _prod(self,l,r,node,a,b):
        if node is None or b<=l or r<=a:
            return self.e
        if l<=a and b<=r:
            return node.v
        m=(a+b)//2
        return self.op(self._prod(l,r,node.l,a,m),self._prod(l,r,node.r,m,b))
    def _max_right(self,l,f,node,a,b):
        if node is None or b<=l or f(node.v):
            return b
        if a+1==b:
            return a
        m=(a+b)//2
        res=self._max_right(l,f,node.l,a,m)
        if res!=m:
            return res
        return self._max_right(l,f,node.r,m,b)
    def _min_left(self,r,f,node,a,b):
        if node is None or r<=a or f(node.v):
            return a
        if b-1==a:
            return b
        m=(a+b)//2
        res=self._min_left(r,f,node.r,m,b)
        if res!=m:
            return res
        return self._min_left(r,f,node.l,a,m)
    def set(self,p,x):
        self.root=self._set(p,x,self.root,self.l,self.r)
    def get(self,p):
        return self._get(p,self.root,self.l,self.r)
    def prod(self,l,r):
        return self._prod(l,r,self.root,self.l,self.r)
    def max_right(self,l,f):
        return self._max_right(l,f,self.root,self.l,self.r)
    
def op(x,y):
    return x+y
e=0

n=int(input())
st=SegTree(op,e,10**9+1)
ans=0
for _ in range(n):
    t,*query=map(int,input().split())
    if t==0:
        x,y=query
        st.set(x,st.get(x)+y)
    else:
        l,r=query
        ans+=st.prod(l,r+1)
print(ans)
0