結果

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

ソースコード

diff # 

import math

class SegTree32way:
    class Node:
        def __init__(self, val=None, ch=None, e=0):
            self.val = val if val is not None else e
            self.ch = ch if ch is not None else [None]*32

    def __init__(self, op, e, n):
        self.n = n
        self.op = op
        self.e = e
        self.root = self.Node(e=e)

    def _set(self, idx, val, node, L, R):
        if node is None:
            node = self.Node(e=self.e)
        if R - L == 1:
            node.val = val
            return node
        step = math.ceil((R - L) / 32)
        i = (idx - L) // step
        if i >= 32:
            i = 31
        child_L = L + i * step
        child_R = min(R, L + (i + 1) * step)
        node.ch[i] = self._set(idx, val, node.ch[i], child_L, child_R)
        s = self.e
        for child in node.ch:
            s = self.op(s, child.val if child is not None else self.e)
        node.val = s
        return node

    def set(self, k, x):
        self.root = self._set(k, x, self.root, 0, self.n)

    def _get(self, idx, node, L, R):
        if node is None:
            return self.e
        if R - L == 1:
            return node.val
        step = math.ceil((R - L) / 32)
        i = (idx - L) // step
        if i >= 32:
            i = 31
        child_L = L + i * step
        child_R = min(R, L + (i + 1) * step)
        return self._get(idx, node.ch[i], child_L, child_R)

    def get(self, k):
        return self._get(k, self.root, 0, self.n)

    def _prod(self, ql, qr, node, L, R):
        if qr <= L or R <= ql:
            return self.e
        if ql <= L and R <= qr:
            return node.val if node is not None else self.e
        res = self.e
        step = math.ceil((R - L) / 32)
        for i in range(32):
            child_L = L + i * step
            if child_L >= R:
                break
            child_R = min(R, L + (i + 1) * step)
            child = node.ch[i] if node is not None else None
            res = self.op(res, self._prod(ql, qr, child, child_L, child_R))
        return res

    def prod(self, l, r):
        return self._prod(l, r, self.root, 0, self.n)
        
def op(x,y):
    return x+y
e=0

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

print(ans)
0