P10436 [JOIST 2024] Card Collection / Card Collection

JOI is passionate about collecting cards in a card game. Each card in the game has two integers representing its strength and cost. To obtain a new card, JOI brings $N$ cards to a card exchange. The cards are numbered from $1$ to $N$. For the $i$-th card ($1 \leq i \leq N$), its strength is $S_i$ and its cost is $V_i$. There are two machines available at the exchange. If you insert two cards $A$ and $B$ into one of the machines, you can obtain a card $C$ that satisfies the following: - If you use the first machine, then the strength of $C$ is the maximum of the strengths of $A$ and $B$, and the cost of $C$ is the maximum of the costs of $A$ and $B$. - If you use the second machine, then the strength of $C$ is the minimum of the strengths of $A$ and $B$, and the cost of $C$ is the minimum of the costs of $A$ and $B$. JOI plans to use these machines exactly $N - 1$ times to obtain one new card. To do this, he arranges the $N$ cards in order from card $1$ to card $N$. Then, he repeats the following operation $N - 1$ times: - Choose two adjacent cards, use one of the machines to obtain a new card, and place the new card at the position of the two chosen cards before the operation. After performing $N - 1$ operations, JOI will have only one card left. The strength and cost of this card depend on the operations he performs. JOI has a list of cards that he hopes to obtain after performing $N - 1$ operations. The $j$-th card ($1 \leq j \leq M$) is represented by a pair of integers $(T_j, W_j)$, where $T_j$ is its strength and $W_j$ is its cost. Write a program that, given information about JOI's cards and the list of cards he wants, determines which cards in the list he can obtain after performing $N - 1$ operations.

Read the following data from standard input. - $N$ $M$ - $S_1$ $V_1$ - $S_2$ $V_2$ - ... - $S_N$ $V_N$ - $T_1$ $W_1$ - $T_2$ $W_2$ - ... - $T_M$ $W_M$

Write one line to standard output. The output should contain, in increasing order, the indices of all cards in the list that JOI can obtain after performing $N - 1$ operations.

#### Sample Explanation 1 For example, JOI can obtain a card with strength 2 and cost 3 in the following way: - Trade in card 4 and card 5 to obtain a card with strength 1 and cost 1. - Trade in card 3 and the card obtained in the first operation to obtain a card with strength 1 and cost 1. - Trade in card 1 and card 2 to obtain a card with strength 2 and cost 3. - Trade in the cards obtained in the second and third operations to obtain a card with strength 2 and cost 3. Note that even if a card with strength 2 and cost 3 is obtained in the third operation, JOI still needs to perform the last operation. Even if a certain card is obtained after some operations, it may still be impossible to obtain it after performing all $N - 1$ operations. The sample input satisfies the constraints of all subtasks. #### Sample Explanation 2 As in this sample output, if it is impossible to obtain any card in the list after performing $N - 1$ operations, output an empty line. The sample input satisfies the constraints of all subtasks. #### Sample Explanation 3 The sample input satisfies the constraints of all subtasks. ### Constraints - $2 \leq N \leq 200,000$. - $1 \leq M \leq 200,000$. - $1 \leq S_i \leq 10^9$ ($1 \leq i \leq N$). - $1 \leq V_i \leq 10^9$ ($1 \leq i \leq N$). - $1 \leq T_j \leq 10^9$ ($1 \leq j \leq M$). - $1 \leq W_j \leq 10^9$ ($1 \leq j \leq M$). - All given values are integers. ### Subtasks 1. (11 points) $N \leq 20$, $M \leq 10$. 2. (38 points) $N \leq 2,000$, $M \leq 10$. 3. (22 points) $M \leq 10$. 4. (29 points) No additional constraints. Translated by ChatGPT 5