aquarelle — IATI junior
Task type: batch | Time limit: 0.35 s | Memory limit: 256 MB | Difficulty: 25
Algorithms: graph search, precomputation, data structures, dynamic programming

# XV INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS SHUMEN 2024

# Task 1. AQUARELLE

⏳ 0.35 sec. 💾 256 MB

Marincho has a new passion - he loves to paint with watercolors. Now he wants to make a color sequence of $N$ cells. For each cell $i$ ($1 \le i \le N$), Marincho has chosen a set of colors $A_i$ of size $K_i$, which he will mix, to paint the cell fulfilling his aesthetic feel. He has already done an initial painting of all cells numbered from $l$ to $r$ in the described manner and is now about to paint the

![](_page_0_Picture_4.jpeg)

remaining cells. Marincho follows a strictly defined order of painting the cells - the next cell that can be painted will be the one with number $l - 1$ or $r + 1$ (if they exist). Formally, if he has already painted all cells numbered from $L$ to $R$, then the next possible cells to paint are:

*   If $L = 1$ and $R = N$, then all cells have been painted.
*   If $L = 1$ and $R < N$, then the next cell, which can be painted, is the one with number $R + 1$.
*   If $L > 1$ and $R = N$, then the next cell, which can be painted, is the one with number $L - 1$.
*   If $L > 1$ and $R < N$, then the next cell, which can be painted, is the one with number $L - 1$ or $R + 1$.

Unfortunately, after Marincho has painted the cells numbered from $l$ to $r$ according to the corresponding sets $A_l, A_{l+1}, \dots, A_r$, Marincho thinks that the sequence has become too monochromatic. Therefore, he decided that for every next cell he paints, there has to be at least one new color, which hasn't been used in the painted cells until now. Help Marincho by writing a program **aquarelle** that finds whether it is possible to paint the remaining cells. Also, you have to find the answer for a few initial paintings - $Q$ pairs $l$ and $r$.

### Input

The first line of the standard input contains the positive integer $N$ - the number of cells. The following $N$ lines contain $K_i$ and $c_1, c_2, ..., c_{K_i}$ which describe the number of colors of the corresponding set $A_i$ and the colors themselves (the colors are different positive integers). The next line contains the positive integer $Q$ - the number of initial paintings. The last $Q$ lines contain pairs of positive integers $l$ and $r$ that specify which sequence has been painted initially.

The numbers in each line are separated by one space.

### Output

For each initial painting, in input order, print 1, if it is possible to finish the painting or 0 otherwise.

### Constraints

*   $1 \le N \le 5 \times 10^5$
*   $1 \le K_i \le 1.2 \times 10^6$, $K_1 + K_2 + \dots + K_N \le 1.2 \times 10^6$
*   $1 \le c_j \le 10^6$
*   $1 \le l \le r \le N$
*   $1 \le Q \le 5$

### Subtasks

| Subtask | Points | Required subtasks | $N$                  | $K_1 + \ldots + K_N$   | Other constraints |
| :-------: | :----: | :----------------: | :-------------------: | :---------------------: | :------------------: |
|     1     |   0    |         -          |          -          |           -           |    The example test.    |
|     2     |   11   |         1          |     $\le 15$     |      $\le 25$      |          -          |
|     3     |   18   |        1 - 2       |     $\le 500$    |     $\le 1100$    |          -          |
|     4     |   24   |        1 - 3       |    $\le 3000$   |   $\le 5 \times 10^5$  |          -          |
|     5     |   36   |        1 - 4       |    $\le 10^5$   |   $\le 5 \times 10^5$  |          -          |
|     6     |   11   |        1 - 5       |   $\le 5 \times 10^5$  |  $\le 1.2 \times 10^6$ |          -          |

*The points for a subtask are given only if all tests for it and the required subtasks are passed successfully.*

### Example

| Input | Output | Explanation of the example                                                                                                                                                                        |
| :---- | :----- | :------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ |
| 6     | 1      | Let we analyze the first initial painting. Optimal sequence of paintings is described in the following table.                                                                                    |
| 2 5 3 | 1      |                                                                                                                                                                                                 |
| 1 4   | 0      |                                                                                                                                                                                                 |
|       |        | Painted cells | Remaining paints | Paint                                                                                                                                                         |
| 1 1   |        | 3, 4          | 3, 4, 5, 6       | The cell with number 2.                                                                                                                                       |
| 1 2   |        | 2, 3, 4       | 3, 5, 6          | The cell with number 5.                                                                                                                                       |
| 2 3 4 |        | 2, 3, 4, 5    | 5, 6             | The cell with number 1.                                                                                                                                       |
| 1 6   |        | 1, 2, 3, 4, 5 | 6                | The cell with number 6.                                                                                                                                       |
| 3     |        | 1, 2, 3, 4, 5, 6| -                | We have made a successful painting of all cells.                                                                                                              |
| 3 4   |        | Note that if we painted the cell with number 5, at first, we would not have been able to successfully paint all cells.                                                                          |
| 2 3   |        | Let we analyze the third initial painting.                                                                                                                                                      |
| 5 5   |        | Painted cells | Remaining paints | Paint                                                                                                                                                         |
|       |        | 5             | 1, 2, 5, 6       | The cell with number 4.                                                                                                                                       |
|       |        | 4, 5          | 1, 5, 6          | The cell with number 3.                                                                                                                                       |
|       |        | 3, 4, 5       | 5, 6             | The cell with number 6.                                                                                                                                       |
|       |        | 3, 4, 5, 6    | 5                | We cannot continue the painting.                                                                                                                              |
|       |        | Note that if we painted the cell with number 6, at first, then the next paintings would have been the same and we would still fail. Therefore, the answer here is 0.                          |

Starter code: