結果

問題 No.789 範囲の合計
ユーザー FuyuruFuyuru
提出日時 2024-02-23 12:37:49
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,914 bytes
コンパイル時間 715 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 151,068 KB
最終ジャッジ日時 2024-02-23 12:37:55
合計ジャッジ時間 4,536 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,460 KB
testcase_01 AC 39 ms
53,460 KB
testcase_02 MLE -
testcase_03 AC 152 ms
75,668 KB
testcase_04 MLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 AC 126 ms
75,656 KB
testcase_08 MLE -
testcase_09 MLE -
testcase_10 AC 286 ms
115,476 KB
testcase_11 MLE -
testcase_12 MLE -
testcase_13 AC 36 ms
53,460 KB
testcase_14 AC 36 ms
53,460 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)
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