시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 1024 MB | 58 | 7 | 6 | 14.634% |
You are given a positive integer $n$ and a sequence $a_1, a_2, \dots , a_n$ of positive integers, such that $\frac{i(i−1)}{2} < a_i \le \frac{i(i+1)}{2}$.
The sequence parameterizes a tree with $\frac{(n+1)(n+2)}{2}$ vertices, consisting of $n + 1$ levels with $1, 2, \dots , n + 1$ vertices, in the following way:
The tree parameterized by $a = (1, 2, 6)$.
The $i$-th level contains vertices $\frac{i(i−1)}{2} + 1, \dots , \frac{i(i+1)}{2}$. The vertex $a_i$ has two children, and the rest of the vertices on the level have one child each.
We want to answer $q$ queries of the form “what is the largest common ancestor of $x$ and $y$”, i.e. the vertex with the largest label which is an ancestor of both $x$ and $y$.
The first line contains integers $n$, $q$ and $t$ ($1 \le n, q \le 200 000, t \in \{0, 1\}$), the number of parameters, the number of queries, and a value which will be used to determine the labels of vertices in the queries.
The second line contains a sequence of $n$ integers $a_i$ ($\frac{i(i−1)}{2} \le a_i \le \frac{i(i+1)}{2}$) which parameterize the tree.
The $i$-th of the following $q$ lines contains two integers $\tilde{x}_i$ and $\tilde{y}_i$ ($1 ≤ \tilde{x}_i, \tilde{y}_i ≤ \frac{(n+1)(n+2)}{2}$) which will be used to determine the labels of vertices in the queries.
Let $z_i$ be the answer to the $i$-th query, and let $z_0 = 0$. The labels in the $i$-th query $x_i$ and $y_i$ are:
$x_i = \left(\left(\tilde{x}_i - 1 + t \cdot z_{i-1}\right) \mod \frac{(n+1)(n+2)}{2}\right) + 1 \text{,}$
$y_i = \left(\left(\tilde{y}_i - 1 + t \cdot z_{i-1}\right) \mod \frac{(n+1)(n+2)}{2}\right) + 1 \text{,}$
where $\text{mod}$ is the remainder of integer divison.
Remark: Note that if $t = 0$, it holds $x_i = \tilde{x}_i$ and $y_i = \tilde{y}_i$, so all queries are known from input. If $t = 1$, the queries are not known in advance, but are determined using answers to previous queries.
Output $q$ lines. In the $i$-th line, output the largest common ancestor of $x_i$ and $y_i$.
번호 | 배점 | 제한 |
---|---|---|
1 | 10 | $q = 1$, $t = 0$ |
2 | 10 | $n ≤ 1000$, $t = 0$ |
3 | 30 | $t = 0$ |
4 | 60 | $t = 1$ |
3 5 0 1 2 6 7 10 8 5 6 2 9 10 2 3
1 5 1 6 1
3 5 1 1 2 6 7 10 8 5 6 2 9 10 2 3
1 6 2 1 1
Clarification of the examples: The tree from both examples is shown on the figure in the statement. Labels of verticies in queries in the second example are: $x_1 = 7, y_1 = 10, \\ x_2 = 9, y_2 = 6,\\ x_3 = 2, y_3 = 8,\\ x_4 = 1, y_4 = 2,\\ x_5 = 3, y_5 = 4$.