← 返回题目列表

Codeforces · 2079/A

A. Alice、Bob 和两个数组

中文机器翻译题面 查看原题

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

Alice, Bob, And Two Arrays - 原题 PDF 第 1 页
原题PDF第1页
Alice, Bob, And Two Arrays - 原题 PDF 第 2 页
原题PDF第2页
Alice, Bob, And Two Arrays - 原题 PDF 第 3 页
原题PDF第3页
可复制的 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