AtCoder Beginner Contest 417
翻译中…
Problem Statement
翻译中…
Define strings $S_0$ and $S_1$ as $S_0=$ 0 and $S_1=$ 1.
翻译中…
You are given $Q$ queries, so process them in order.
In the $i$-th query $(1\leq i\leq Q)$, you are given a triple of integers $(L_i,R_i,X_i)$.
翻译中…
Let
$S_{i+1}$be the string obtained by concatenating$S_{L_i}$and$S_{R_i}$in this order. Then, find the$X_i$-th character of$S_{i+1}$.It is guaranteed that
$X_i$is at most the length of$S_{i+1}$.
翻译中…
Constraints
翻译中…
$1\leq Q\leq 5\times 10^5$$0\leq L_i,R_i\leq i$$1\leq X_i\leq 10^{18}$$X_i$is at most the length of$S_{i+1}$.- All input values are integers.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
Q
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_Q R_Q X_Q翻译中…
Output
翻译中…
Output $Q$ lines. The $i$-th line $(1\leq i\leq Q)$ should contain the answer to the $i$-th query.
翻译中…
样例
Input #1
7
0 1 1
0 0 2
1 1 1
2 3 2
2 4 3
5 4 2
6 7 6
Output #1
0
0
1
1
1
1
1
Each query is processed as follows:
- In the first query, concatenate $S_0=$`0` and $S_1=$`1` to get $S_2=$`01`. The first character of $S_2$ is `0`, so output $0$ on the first line.
- In the second query, concatenate $S_0=$`0` and $S_0=$`0` to get $S_3=$`00`. The second character of $S_3$ is `0`, so output $0$ on the second line.
- In the third query, concatenate $S_1=$`1` and $S_1=$`1` to get $S_4=$`11`. The first character of $S_4$ is `1`, so output $1$ on the third line.
- In the fourth query, concatenate $S_2=$`01` and $S_3=$`00` to get $S_5=$`0100`. The second character of $S_5$ is `1`, so output $1$ on the fourth line.
- In the fifth query, concatenate $S_2=$`01` and $S_4=$`11` to get $S_6=$`0111`. The third character of $S_6$ is `1`, so output $1$ on the fifth line.
- In the sixth query, concatenate $S_5=$`0100` and $S_4=$`11` to get $S_7=$`010011`. The second character of $S_7$ is `1`, so output $1$ on the sixth line.
- In the seventh query, concatenate $S_6=$`0111` and $S_7=$`010011` to get $S_8=$`0111010011`. The sixth character of $S_8$ is `1`, so output $1$ on the seventh line.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。