結果

問題 No.789 範囲の合計
コンテスト
ユーザー Fuyuru
提出日時 2024-02-23 12:37:49
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,914 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 152,164 KB
最終ジャッジ日時 2024-09-29 05:03:23
合計ジャッジ時間 4,276 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 MLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
class Node:
    def __init__(self):
        self.val = 0
        self.left = None
        self.right = None
class BinaryTrie:
    def __init__(self,max_size):
        self.s = max_size.bit_length()
        self.root = Node()
    def __getitem__(self,x):
        node = self.root
        tmp = 1<<(self.s-1)
        for i in range(self.s):
            if x&tmp:
                if node.right is None:
                    return 0
                node = node.right
            else:
                if node.left is None:
                    return 0
                node = node.left
            tmp >>= 1
        return node.val
    def add(self,x,val):
        node = self.root
        tmp = 1<<(self.s-1)
        for i in range(self.s):
            node.val += val
            if x&tmp:
                if node.right is None:
                    node.right = Node()
                node = node.right
            else:
                if node.left is None:
                    node.left = Node()
                node = node.left
            tmp >>= 1
        node.val += val
    def fold_(self,r):
        node = self.root
        res = 0
        tmp = 1<<(self.s-1)
        for i in range(self.s):
            if r&tmp:
                if node.right is None:
                    return res+node.left.val
                res += node.val-node.right.val
                node = node.right
            else:
                if node.left is None:
                    return res
                node = node.left
            tmp >>= 1
        return res
    def fold(self,l,r):
        return self.fold_(r)-self.fold_(l)
    def all_prod(self):
        return self.root.val


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