LCC '23 Contest 3 J4 - Christmas Dinner Platters

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 256M

Problem type

After a chilly snowball fight, Elsa and Anna return to their castle to dry themselves off. They are greeted by the smell of their favorite dishes wafting out from the dining hall; the Christmas dinner is ready! They run into the dining hall and see a row of platters arranged along the long, wooden dinner table.

Anna excitedly taps Elsa on the shoulder and exclaims:

Look at those platters of roast beef, potatoes, corn, pudding and gingerbread! Yummy~

Elsa replies:

Indeed, there exists several plates filled with a variety of nourishment, my sibling. More specifically, I have observed that there are N (1 \le N \le 10^6) platters, each of them containing the a_i-th type of food (1 \le a_i \le N). Upon further careful observation of the behaviour of the guests, I have come to the following conclusion: To get food, one lines up with their plate, initially empty, at the beginning of the table, and walks, starting from the 1st dish, forward along the table. At each dish i from 1 to N, one can either choose to stack the a_i-th food on top of their plate (i.e. on top of everything before it), or they can skip over it. However, one cannot turn backwards, and once they finish walking along the table, they cannot go back.

Anne wonders:

Wow, cool! Do ya think I can get my plate to be stacked in a specific way, just how I like it?

She then proceeds to list M (1 \le M \le 100) orders, where the i-th order consists of K_i dishes, in order from top to bottom of the finished plate. Please help Elsa determine whether each of Anna's orders is possible to stack.


1 \le a_i \le N \le 10^4

1 \le M \le 100

1 \le K_i \le 5 \times 10^3

Input Specifications

The first line will contain two integers, N and M.

The second line will contain N integers, representing a_i.

On the next M lines, there will first be an integer K_i, then K_i integers, representing Anna's order, from top to bottom.

Output Specifications

For each order, output YES if the order can be made, or NO otherwise.

Sample Input 1

6 3
6 4 5 5 1 2
3 2 4 6
4 2 5 4 5
2 5 5

Sample Output 1


Sample Explanation 1

For the first query, Anna can pick up food from plates 1, 2, and 6.

For the second query, there is no possible way (especially since the two 5's are consecutive in the plates, but they are separated by a 4 in her order).

For the third query, Anna can pick up food from plates 2 and 3.


There are no comments at the moment.