Spaceship can go only forward, so check - there shouldn't be any backward movement. Test #5 is about that.

Edited by author 05.10.2023 14:33

i know it....something wrong with my brain.

What!@

is there simpler solution?? I use brute_force search....

<3 <3 <3

Thanks it was rounding error

I did it with sqrt(N) blocks, and got tl on 11 too

I know it's an old thread, but it's how I solved it.
So spoilers and all.
if l->r is even, then s[r] and s[l - 1] have the same parity (where s[x] is the partial sum of bits from 1 to x)
if l->r is odd, then they have opposite parities
We add l-1 and r to a dsu. So a dsu is just a tree of all dependencies, no matter if odd or even (see how I differentiate between the two below).

I used dsu with an added property that is only available for dsu roots:
sons[root][0] is the "representative" of all elements that have the same parity of root, sons[root][1] is the "representative" of all elements that have opposite parity of root.
Anything else besides the root->representative edges will only have 0s, codifying that entire subtrees have the same parity.

So first off when you do find, I haven't really bothered with path compression. And instead of just saying what is the dsu root for a node, you also say which side it came from (0 if it came from sons[root][0] and 1 for sons[root][1]) - so (0, root) means it has the same parity as root and (1, root) means it has opposite parities.

So now when you do union, you first have a small case, if the two nodes are already in a tree, you have to verify that the sides they're on match the parity of s[r] - s[l - 1] otherwise you stop at the current test.

Now, if they're not yet united, you have 4 cases that are basically just 2:
if l-1 and r are on the same side of their respective dsus with s[r]-s[l-1] even, then this is one case
if l-1 and r are on opposite sides of their respective dsus with s[r]-s[l-1] odd, then this is one case(identical with the previous one)

And of course you have the opposite cases as well, which form another case you have to treat separately.

So now you just have to move the left and right sides from one tree to the other so that they all match up correctly. You can do this however you like, just make sure that the property we've added to the dsu (sons is a unique property of the root of a dsu) is kept.

Here's how I did it (let's treat just the case where l->r is even and l-1 and r are on the 0 sides of their respective dsus), and let's say l - 1 has root T1 and r root T2, we want to join the tree T2 into tree T1.

        T1          T2
     0/   \1      0/  \1
     a     b      c    d
     |     |      |    |
     A     B      C    D  (l - 1 comes from A, r comes from C)

a, b, c, d are representatives of A, B, C, D.
And this is how the finalized tree will Look:

               T1
            0/   \1
            T2    d
           0|\0   |\
            a c   D b
            | |     |
            A C     B
As you can see, since T2 is no longer a root, sons[T2] becomes redundant since it's gonna have 0's on the edges which is what keeps the property.
For the opposite case, you do something similar, just that T2 will be on the 1 side of T1 and you play around with the representatives.
Of course there are some cases where some roots don't yet have both/any sons, but it's not too ugly to deal with them.

Also for implementation, I normalized values but I think you could just use unordered_map/map.