結果

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

ソースコード

diff # 

class SegTree:
    class Node:
        def __init__(self, pos, val):
            self.pos = pos
            self.val = val
            self.agg = val
            self.l = None
            self.r = None

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

    def _set(self, p, x, node, l, r):
        if r - l == 1:
            if x == self.e:
                return None
            return self.Node(p, x)
        m = (l + r) // 2
        if node is None:
            node = self.Node(-1, self.e)
        if p < m:
            node.l = self._set(p, x, node.l, l, m)
        else:
            node.r = self._set(p, x, node.r, m, r)
        left_val = node.l.agg if node.l is not None else self.e
        right_val = node.r.agg if node.r is not None else self.e
        node.agg = self.op(left_val, right_val)
        if node.agg == self.e and node.l is None and node.r is None:
            return None
        return node

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

    def _get(self, p, node, l, r):
        if node is None:
            return self.e
        if r - l == 1:
            return node.val
        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 get(self, p):
        return self._get(p, self.root, 0, self.n)

    def _prod(self, ql, qr, node, l, r):
        if node is None or qr <= l or r <= ql:
            return self.e
        if ql <= l and r <= qr:
            return node.agg
        m = (l + r) // 2
        left_prod = self._prod(ql, qr, node.l, l, m)
        right_prod = self._prod(ql, qr, node.r, m, r)
        return self.op(left_prod, right_prod)

    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 = SegTree(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