I got MLE in this submission. After investigation it turned out that I created empty containers before a recursive call (in the get_delete_x_ans function), resulting in creation of many such containers when call stack is deep.

That sounds reasonable, but when I did the calculation, it seemed impossible that this mistake could lead to MLE when the mem limit is 512MB.

So the calculation goes:

My later accepted solution uses 175100KB, limit is ~524288KB, difference is 300000+KB = approx. 300MB.

So it means that the submission above created empty containers that take up 300MB space.

It will create 2 empty queue, each is 48 byte on a 64-bit machine.

Recursion depth is <=500000 from problem description. So total space of empty containers is 2 x 48B x 500000 = approx. 5x10^7 B = 50MB.

That's much less than 300MB, so if the calculation was correct, I shouldn't get MLE.

Can someone help point out what's wrong with my calculation above? Thanks!

Original problem: 1592E - Bored Bakry

I somehow misread the problem into this: you are required to find a subsequence [L,R], such that the value $$$a_L & ... & a_R - a_L ^ ... ^ a_R$$$ is maximized.

I only come up with a O(nlognlogV) solution, where V is maximum value that an $$$a_i$$$ can take.

Here's my solution:

First, suppose we consider all possible subsequences with left endpoint L.

Since as r increase, AND(L,r) decrease, and there are only logV possible different values for it, we can divide all possible r values into logV segments, within each AND(L,r) is constant.

Now we need to find least value for XOR(L,r) in each segment. Note that XOR(L,r) = PREFIX_XOR(r) ^ PREFIX_XOR(L-1), if we have a Trie tree for each PREFIX_XOR(i) in the segment, walking on it according to digits of PREFIX_XOR(L-1) yields the least XOR.

However we cannot afford to build Trie tree for every query. We can build a segment tree for segment (1,n), and build a Trie tree for each segment tree node. That way both space and time complexity will be O(nlognlogV).

I'm not sure if algorithms with better complexity exist, can u guys help me?