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



可复制的 PDF 提取文本
Open Olympiad in Informatics 2024/25. First day
Moscow, March 7th, 2025
Problem Wood. Alice, Bob, and two arrays.
Input file: input.txt or standard input
Output file: output.txt or standard output
Time limit: 2.5 seconds
Memory limit: 1024 megabytes
There is an array a of length N and an array b of length M. All numbers in the arrays are integers and
lie in the range from 1 to k. There is also an initially empty array c.
Alice and Bob play the following game on these arrays: the players take turns, and on their turn, a player
must append a number to the end of the array c such that c remains a subsequence of both a and b. The
player who cannot make a move loses. Alice goes first.
They will play the game q times. For the i-th game, they will choose two numbers xi and yi
(0 ≤xi < N, 0 ≤yi < M), then remove the first xi elements from array a and the first yi elements
from array b, and then play the game on the resulting arrays. After each deletion operation and before the
next one, the arrays a and b are restored to their initial state, meaning that the numbers deleted from the
arrays in one game may not be deleted in subsequent games. Also, the array c is cleared between games.
The guys have their quirks, so they always choose xi and yi in such a way that after the deletions, the
remaining parts of arrays a and b start with the same value.
Alice really wants to win, so she asks you to determine for each game whether she can win, assuming both
players play optimally.
Note that the arrays can be very long, so they are provided in a special format. Each array is given as a
sequence of segments of equal numbers. Array a consists of n such segments, and array b consists of m
such segments. Each segment is defined by its length and the number that occupies that segment.
Input
The first line contains six integers N, n, M, m, k, q (1 ≤N, M ≤109, 1 ≤n, m, k ≤1600, 1 ≤q ≤106)
— the length of the first array, the number of segments in the first array, the length of the second array,
the number of segments in the second array, the number limit, and the number of games, respectively.
The next n lines contain two integers lai and vai (1 ≤lai ≤N, 1 ≤vai ≤k) — the length of the segment
and the number written in that segment. These numbers define array a: the first la1 numbers of array a
are equal to va1, the next la2 numbers are equal to va2, . . ., the last lan numbers are equal to van.
The next m lines contain two integers lbi and vbi (1 ≤lbi ≤N, 1 ≤vbi ≤k) — the length of the segment
and the number written in that segment. These numbers define array b. The format is similar to array a.
It is guaranteed that P lai = N, P lbi = M, vai ̸= vai+1, and vbi ̸= vbi+1.
The next q lines contain pairs of integers xi and yi (0 ≤xi < N, 0 ≤yi < M) — descriptions of the
games.
For each game i, it is guaranteed that if we remove the first xi elements from a and the first yi elements
from b, the remaining parts of the arrays will start with the same value.
Output
For each of the q games, print “Yes“ if Alice wins with optimal strategy, and “No“ if Bob wins.
Page 1 of 9
Open Olympiad in Informatics 2024/25. First day
Moscow, March 7th, 2025
Examples
input output
5 1 5 1 1 9 Yes
5 1 No
5 1 Yes
0 0 No
0 1 No
0 2 Yes
1 0 Yes
1 1 Yes
1 2 Yes
2 0
2 1
2 2
7 3 7 3 2 12 Yes
2 1 No
3 2 Yes
2 1 Yes
2 2 No
3 1 Yes
2 2 No
0 2 Yes
0 3 No
0 4 Yes
1 2 Yes
1 3 Yes
1 4
2 5
2 6
3 5
3 6
4 5
4 6
Note
In the first example, the arrays look like this: a = (1, 1, 1, 1, 1) and b = (1, 1, 1, 1, 1).
• In the first query, x = 0, y = 0, so the game will be played on the arrays a = (1, 1, 1, 1, 1) and
b = (1, 1, 1, 1, 1). In this case, players can only append the number 1 to the array c, so after 5 moves
the game will end, and Bob will lose because he won’t be able to make a move.
• In the second query, x = 0, y = 1, so the game will be played on the arrays a = (1, 1, 1, 1, 1) and
b = (1, 1, 1, 1). In this case, the game will end after 4 moves, and Alice will lose.
• In the last query, x = 2, y = 2, so the game will be played on the arrays a = (1, 1, 1) and b = (1, 1, 1).
In this case, Bob will lose.
In the second example, a = (1, 1, 2, 2, 2, 1, 1), b = (2, 2, 1, 1, 1, 2, 2).
• In the first query, x = 0 and y = 2, so the game will be played on the arrays a = (1, 1, 2, 2, 2, 1, 1)
and b = (1, 1, 1, 2, 2). If Alice appends the number 2 to the array c, Bob will also append the number
2, and then no moves will be left, so Alice will lose. Therefore, Alice must first append the number
Page 2 of 9
Open Olympiad in Informatics 2024/25. First day
Moscow, March 7th, 2025
1 to c. After this, for similar reasons, if Bob appends the number 2 to the array, he will lose. So,
he is forced to append the number 1, and the array c becomes (1, 1). Then Alice again appends the
number 1 to the array c, and Bob has no more moves left, so Alice wins.
• In the second query, x = 0 and y = 3, so the game will be played on the arrays a = (1, 1, 2, 2, 2, 1, 1)
and b = (1, 1, 2, 2). Following the reasoning in the previous example, Alice cannot append the
number 2 to the array c, because then she will lose. But if Alice appends the number 1, then Bob
will also append the number 1, and after that, Alice will lose for similar reasons. Therefore, Bob
wins in this case.
Scoring
The tests for this problem consist of eleven 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, M n, m q
0 0 – – – – Examples.
1 13 N, M ≤300 – q ≤105 0
2 12 N, M ≤5000 – q ≤105 0, 1
lai ≤1000 and all vai are distinct 3 11 – – q ≤105 –
lbi ≤1000 and all vbi are distinct
4 8 – – q ≤105 3 lai ≤1000 and all vai are distinct
la1 ≥N −500 and va1 = 1 5 10 – – q ≤105 –
lb1 ≥M −500 and vb1 = 1
6 7 N, M ≤105 n, m ≤100 q ≤105 – k ≤5
7 6 N, M ≤105 n, m ≤100 q ≤105 0, 6 k ≤50
8 7 – n, m ≤100 q ≤105 0, 6, 7 k ≤50
9 9 – n, m ≤800 q ≤105 0, 6 – 8
10 10 – – q ≤105 0 – 9 Offline-evaluation.
11 7 – – – 0 – 10 Offline-evaluation.
Page 3 of 9