BareLee
Contest: Codeforces Round 652 (Div. 2)
Difficulty rating: 2700
Tags: dfs and similar, dp, games

Lee is used to finish his stories in a stylish way, this time he barely failed it, but Ice Bear came and helped him. Lee is so grateful for it, so he decided to show Ice Bear his new game called "Critic"...

The game is a one versus one game. It has $$$t$$$ rounds, each round has two integers $$$s_i$$$ and $$$e_i$$$ (which are determined and are known before the game begins, $$$s_i$$$ and $$$e_i$$$ may differ from round to round). The integer $$$s_i$$$ is written on the board at the beginning of the corresponding round.

The players will take turns. Each player will erase the number on the board (let's say it was $$$a$$$) and will choose to write either $$$2 \cdot a$$$ or $$$a + 1$$$ instead. Whoever writes a number strictly greater than $$$e_i$$$ loses that round and the other one wins that round.

Now Lee wants to play "Critic" against Ice Bear, for each round he has chosen the round's $$$s_i$$$ and $$$e_i$$$ in advance. Lee will start the first round, the loser of each round will start the next round.

The winner of the last round is the winner of the game, and the loser of the last round is the loser of the game.

Determine if Lee can be the winner independent of Ice Bear's moves or not. Also, determine if Lee can be the loser independent of Ice Bear's moves or not.

Input format:
The first line contains the integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of rounds the game has.

Then $$$t$$$ lines follow, each contains two integers $$$s_i$$$ and $$$e_i$$$ ($$$1 \le s_i \le e_i \le 10^{18}$$$) — the $$$i$$$-th round's information.

The rounds are played in the same order as given in input, $$$s_i$$$ and $$$e_i$$$ for all rounds are known to everyone before the game starts.

Output format:
Print two integers.

The first one should be 1 if Lee can be the winner independent of Ice Bear's moves, and 0 otherwise.

The second one should be 1 if Lee can be the loser independent of Ice Bear's moves, and 0 otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Remember, whoever writes an integer greater than $$$e_i$$$ loses.

Example input:
3
5 8
1 4
3 10

Example output:
1 1

Example input:
4
1 2
2 3
3 4
4 5

Example output:
0 0

Editorial:
$$$\mathcal Complete \mathcal Proof$$$ :
Define $$$w_{s,\,e}$$$ ($$$s \le e$$$) equal to $$$1$$$ if Lee can win the game when $$$s$$$ is written on the board, and equal to $$$0$$$ otherwise, also define $$$l_{s,\,e}$$$ the same way. This leads to a simple dp. Forget $$$l$$$ for now.
Recall that a state $$${i,\,j}$$$ of our dp is a losing state if $$$w_{i,\,j} = 0$$$, and is a winning state otherwise.
You can guess $$$w_{s,\,e}$$$ for all $$$s$$$ in range $$$\frac e 4 < s \le e$$$ in $$$O(1)$$$, you don't have to store them :
If $$$e$$$ is odd then it will be $$$w_{1,\,e} = 1, w{2,\,e} = 0, w{3,\,e} = 1 \dots w{e,\,e} = 0$$$, in other words if $$$e$$$ is odd, then if $$$s$$$ is odd too $$$w{s,\,e} = 0$$$, otherwise $$$w{s,\,e} = 1$$$. Prove it by induction, for $$$s = e$$$ it's correct, assume that for an integer $$$i$$$ ($$$1 \le i < e$$$) we have proved that the statement is correct for all $$$j$$$ where $$$i < j \le e$$$, now we want to prove the statement for $$$i$$$ :
If $$$i$$$ is odd then both $$$i + 1$$$ and $$$2 \cdot i$$$ are winning states (as they are even), also if $$$i$$$ is even then $$$i + 1$$$ is odd, $$$i+1$$$ is smaller than $$$e$$$ so it's a losing state(induction assumption).
From now we consider $$$e$$$ to be even. Also $$$\times 2$$$ operation is replacing $$$a$$$, the number on the board, with $$$2 \cdot a$$$, and $$$+ 1$$$ operation is the other move.
For $$$\frac e 2 < s \le e$$$ whoever uses $$$\times 2$$$ operation will lose. So they all have to use $$$+ 1$$$ operation, so for $$${e \over 2} < s \le e$$$ if $$$w$$$ is odd, then $$$w_{s,\,e} = 1$$$, otherwise $$$w_{s,\,e} = 0$$$. (it's obvious, it can be proved with a simple induction like the one in previous part)
For $$${e \over 4} < s \le {e \over 2}$$$, Lee can do a $$$\times 2$$$ operation in the first turn and he will win because his opponent is starting a losing state.
For $$$s \le {e \over 4}$$$, $$$w_{s,\,e}$$$ is equal to $$$\displaystyle w_{s,\,\lfloor {e \over 4} \rfloor}$$$. (why?)
Now it's time to calculate $$$l_{s,\,e}$$$.
Remember, whoever writes an integer greater than $$$e$$$ will lose, so if $$$e < 2 \cdot s$$$ then the first guy can immediately lose. So $$$l_{s,\,e}$$$ for $$${e \over 2} < s \le e$$$ is equal to $$$1$$$. And $$$l_{s,\,e}$$$ for $$$s \le {e \over 2}$$$ is equal to $$$\displaystyle w_{s,\,{\lfloor {e \over 2} \rfloor}}$$$. (why?)