結果

問題 No.789 範囲の合計
ユーザー FuyuruFuyuru
提出日時 2024-02-23 12:36:07
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,900 bytes
コンパイル時間 214 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 149,252 KB
最終ジャッジ日時 2024-09-29 05:03:18
合計ジャッジ時間 3,108 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 AC 38 ms
52,900 KB
testcase_02 RE -
testcase_03 AC 135 ms
76,964 KB
testcase_04 MLE -
testcase_05 MLE -
testcase_06 RE -
testcase_07 AC 108 ms
76,544 KB
testcase_08 RE -
testcase_09 MLE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 AC 36 ms
53,092 KB
testcase_14 AC 33 ms
53,016 KB
権限があれば一括ダウンロードができます

ソースコード

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)
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