https://mirror.codeforces.com/profile/xueshenwudi

my friend was disabled 1-2 years ago,i don't have any idea why,i wanna know the reason too.

In the standard nim game, we xor the values of all piles, and if the xor value is 0, then the first player loses. Otherwise, he has a winning strategy. One variant of the nim game has an extra move that allows players to add positive number of stones to a single pile (given some conditions to make the game finite). The solution for this variant is similar to the standard nim game because this extra move will be used by the winning player, and whenever the losing player does it, the winning player can cancel it by throwing away these added stones.

This problem can be modeled as the mentioned variant. Lets color leaf nodes with blue. The parent of a blue node is red and the parent of a red node is blue (that’s why all paths from root to leaves must have the same parity). Blue nodes are our piles while red nodes allow discarding apples or increasing piles.

If the xor value of blue nodes s = 0, then Soliman loses on the initial tree. To keep this state after the swap, Sagheer can:

swap any two blue nodes or any two red nodes.

swap a blue node with a red node if they have the same number of apples.

If the xor value of blue nodes s ≠ 0, then Sagheer loses on the initial tree. To flip this state after the swap, Sagheer must swap a blue node u with a red node v such that s ^ a[u] ^ a[v] = 0.

Complexity: O(n + maxA) where maxA is the maximum value for apples in a single node.

I use the cube root too.

Split $$$[1,250000]$$$ into blocks size of $$$64$$$ is enough.

What about penalty?

I mean, if i have technical issues and get extra 10 minutes, and i finish problem A at 90 minutes, my final time will be 90 or 80?

If it's 90,will there be another update to manage this setting so that i can calculate my penalty as 80?

As a participant, I wish i can see score distribution RIGHT NOW.XD

L.Lawliet XD

I like "Plants vs. Zombies" very much and I think carts can ko a lot of zombie and they're very useful,so I like them very much and use "Little_CarT" as my username XD

I know most of things you say,but i am still CM lol

ok,thanks.

But i think red&black is much more good-looking actually :D

At least i think so :P

i just want to decorated my name in several days because Christmas is near,i wanna be more Festive (OvO)

But i think red is much more good-looking actually :D

At least i think so :P

Auto comment: topic has been updated by Little_CarT (previous revision, new revision, compare).

Shameless cheaters.

I think people have different opinions in interactive problems.

In my opinion,I like these problems because it's really interesting and it can widen my sight.

Some of these problem really helped me a lot to learn some algorithm that i have never seen.

Although sometimes it makes my rating dropped,I still enjoy it by its interesting,its unique glamour.

PS:I'm bad in English,but I try my best. :p

Obviously the largest glass piece at any moment is the one that is product of the largest horizontal segment by the largest vertical segment. One of the possible solutions is to carefully implement what described in the statement and keep all horizontal segments and all vertical segments in priority queue or std::set, or some logarithmic data structure. This solution works in O (k * log(n + m)).

But there is also a nice linear solution if we answer all queries in reverse order. Suppose segments are not cutting, but merging. In this case we may keep the horizontal and vertical cut lines in double-linked lists and track the current maximum (that can only increase and become equal to the newly-merged segment each time). This solution works in O(k + n + m).