以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。



可复制的 PDF 提取文本
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
Problem C. Burenka and Pether
Input file: standard input
Output file: standard output
Time limit: 3 seconds
Memory limit: 1024 megabytes
Once upon a time, the princess of Burlyandia, Burenka, decided to please her friend ReLu. Knowing that
ReLu shares her interest in cryptocurrency, Burenka decided to create her own blockchain cryptocurrency
called Pether.
After taking courses and training from an expert coach in personal growth in cybersecurity, Burenka
decided that the currency Pether should be protected in the best possible way. As a result, due to
incredibly complex and convoluted restrictions, not all users can exchange Pether with each other.
The structure of the Pether blockchain currency is indeed complex and convoluted. All users are numbered
with integers from 1 to n. Each user is assigned a unique identifier ai. Also, the currency has a security
parameter d.
User i can directly transfer currency to user j only if i < j and ai < aj. But that’s not enough!
Direct currency transfer between users occurs through a chain of transactions involving some number of
intermediate users. During each transaction, the number of each subsequent intermediate user (including
the last user j) must increase, but not by more than d. Also, all intermediate users except i and j must
have an identifier strictly less than ai.
More formally, user i can directly transfer cryptocurrency to user j if the following conditions are met:
1. It is satisfied that i < j
2. It is satisfied that ai < aj
3. There exists a sequence of intermediate users x of length k such that:
(a) i = x1 < x2 < . . . < xk−1 < xk = j
(b) For all 1 ≤t ≤k −1, it is true that xt+1 −xt ≤d
(c) For all 2 ≤t ≤k −1, it is true that axt < ai
Burenka asks you, her acquaintance programmer, to understand this system and find out for some pairs
of users how to transfer Pether to each other.
You need to answer q queries. In each query, you need to determine whether there is a sequence of direct
currency transfers (possibly through intermediate users) that allows transferring Pether from user ui to
user vi. In some queries, it is also necessary to minimize the number of direct currency transfers in the
process of sending currency from ui to vi. Please note that it is not necessary to minimize the number of
transactions during each direct transfer.
Input
The first line contains three integers n, d, and g (1 ≤n, d ≤300 000, 0 ≤g ≤12) — the number of users,
the security parameter, and the test group number.
The second line contains n integers a1, a2, . . . , an (1 ≤ai ≤n) — user identifiers. It is guaranteed that
all numbers ai are distinct.
The third line contains a single integer q (1 ≤q ≤300 000) — the number of queries.
The next q lines contain three integers each ti, ui, vi (ti ∈{1, 2}, 1 ≤ui < vi ≤n), where ui is the
user who should transfer the currency, and vi is the user who should receive the currency. If ti = 1, then
it is necessary to determine whether it is possible to transfer the currency, and if ti = 2, then it is also
necessary to minimize the number of direct currency transfers.
Page 7 of 12
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
Output
Output q lines, where the i-th line should contain the answer to the i-th query.
If it is not possible to transfer the currency from user ui to user vi, then output 0 as the answer to the
i-th query. Otherwise, if ti = 1, output 1, and if ti = 2, output the minimum number of direct currency
transfers required to transfer Pether from ui to vi.
Examples
standard input standard output
6 1 0 1
2 1 3 4 5 6 0
6 1
2 1 3 3
2 1 2 4
1 1 4 1
2 1 5
2 1 6
1 2 6
6 2 0 2
1 2 3 4 5 6 2
6 3
2 1 5 2
2 2 5 2
2 1 6 1
2 2 6
2 1 4
2 2 4
10 2 0 2
2 1 4 3 5 6 8 7 10 9 1
10 1
2 1 5 4
1 2 5 2
2 3 5 3
2 1 9 3
2 5 8 0
2 3 9 2
2 1 8 4
1 1 2
2 3 8
2 1 9
Note
In the first example, the following direct transfers between users are possible:
In the first query, user with index 1 can directly transfer Pether to user with index 3, making 2 transactions
through intermediate user 2.
In the second query, a direct transfer between users with indices 1 and 2 is not possible, as a1 = 2 > a2 = 1.
Page 8 of 12
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
In the third query, it is possible to transfer the currency from user 1 to user 4 with two direct transfers,
first transferring the currency from user 1 to user 3, and then from 3 to 4. Since t3 = 1, it is only necessary
to determine the possibility of transferring the currency, so the answer to the query is 1.
In the fourth query, it is possible to manage with three direct transfers: from 1 to 3, from 3 to 4, and from
4 to 5.
In the second example, the following direct transfers between users are possible:
In the third example, the following direct transfers between users are possible:
Scoring
The tests for this problem consist of twelve groups. Points for each group are given only if all tests of
the group and all tests of the required groups are passed. Please note that passing the example tests is
not required for some groups. Offline-evaluation means that the results of testing your solution on this
group will only be available after the end of the competition.
Additional constraints Required
Group Points Comment
groups n q vi, an, ti
0 0 – – – – Examples.
1 10 n ≤100 q ≤100 – –
2 7 n ≤1000 – – 1
3 14 – – an = n, vi = n –
4 10 – q = 1 vi = n –
5 9 – – vi = n 3, 4
6 7 – – ti = 2 – The answer does not exceed 10
7 7 – – ti = 2 1, 6 The answer does not exceed 150
8 13 – – ti = 1 –
9 10 n ≤50 000 q ≤50 000 – 1
10 4 n ≤100 000 q ≤100 000 – 1, 9
11 4 n ≤200 000 q ≤200 000 – 1, 9, 10
12 5 – – – 0 – 11 Offline-evaluation.
Page 9 of 12