Help me in solving REBXOR problem

help
,
1

My issue

Hey, is it possible to solve this problem using Python or Pypy?

I’ve written a solution which I believe to be O(NlogAmax) as in the solution, but I’m getting timed out:

I can see that the problem has been solved over 1500 times, but none of the solutions are python or pypy. Nearly all of the solutions are C++.

Is it possible to improve the time efficiency of my solution or is the time constraint just too strict for python in this puzzle?

My code

from itertools import accumulate

# cook your dish here
def addToTrie(num, root):
    for i in range(30, -1, -1):
        val = (num >> i) % 2
        if not val in root:
            root[val] = {}
        root = root[val]
        
def searchTrie(num, root):
    res = 0
    for i in range(30, -1, -1):
        val = (num >> i) % 2
        if val ^ 1 in root:
            root = root[val ^ 1]
            res += 1 << i
        else:
            root = root[val]
    return res
    
def helper(arr):
    val = 0
    trie = {}
    res = []
    for item in arr:
        addToTrie(val, trie)
        val ^= item
        res.append(searchTrie(val, trie))
    return list(accumulate(res, max))
    
n = int(input())
arr = list(map(int, input().split()))

left = helper(arr)
right = helper(arr[::-1])[::-1]

print(max(sum(item) for item in zip(left, right[1:])))

Problem Link: Nikitosh and xor Practice Coding Problem - CodeChef