레이팅 미적용4 seconds / 1 GiB / 110 points
You are given a positive integer \(n\) and a sequence \(a_{1}\), \(a_{2}\), . . . , \(a_{n}\) of positive integers, such that ^{i(\(i - 1\))}
2
<
\(a_{i}\) ≤^{i(\(i+1\))}
2
.
The sequence parameterizes a tree with ^{(\(n+1\))(\(n+2\))}
2
vertices, consisting of \(n + 1\) levels with 1, 2, . . . , \(n + 1\)
vertices, in the following way:
1
2
4
7
5
8
3
6
9
10
The tree parameterized by \(a\) = (1, 2, 6).
The \(i\)-th level contains vertices ^{i(\(i - 1\))}
2
+ 1, . . . , ^{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\) ∈{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}\) ( ^{i(\(i - 1\))}
2
< \(a_{i}\) ≤^{i(\(i+1\))}
2
) which parameterize the tree.
The \(i\)-th of the following \(q\) lines contains two integers e\(x_{i}\) and e\(y_{i}\) (\(1 \le ex_{i}\), e\(y_{i}\) ≤^{(\(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}\) =
(e\(x_{i} - 1 + t \cdot z_{i - 1}\)) mod ^{(\(n+1\))(\(n+2\))}
2
+ 1,
\(y_{i}\) =
(e\(y_{i} - 1 + t \cdot z_{i - 1}\)) mod ^{(\(n+1\))(\(n+2\))}
2
+ 1,
where mod is the remainder of integer divison.
Remark: Note that if \(t = 0\), it holds \(x_{i} = ex_{i}\) and \(y_{i} = ey_{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}\).
4 seconds / 1 GiB / 110 points
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(q = 1\), \(t = 0\) |
2 | 10점 | \(n \le 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 31
5
1
6
13 5 1
1 2 6
7 10
8 5
6 2
9 10
2 31
6
2
1
1Clarification 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:
x1 = 7, y1 = 10,
x2 = 9, y2 = 6,
x3 = 2, y3 = 8,
x4 = 1, y4 = 2,
x5 = 3, y5 = 4.