[JOIST 2024] 卡牌收集 / Card Collection

Luogu

IDLGP10436

Time4000ms

Memory1024MB

DifficultyP7

2024JOISC/JOIST（日本）

JOI 君对一款卡牌游戏中的卡牌收集充满热情。卡牌游戏中的每张卡牌都有两个整数，代表其强度和成本。为了获得一张新卡牌，JOI 君将 $N$ 张卡牌带到一个卡牌交换处。每张卡牌编号从 $1$ 到 $N$。第 $i$ 张卡牌（$1 \leq i \leq N$）的强度是 $S_i$，成本是 $V_i$。卡牌交换处有两台机器可供使用。如果你将两张卡牌 $A$ 和 $B$ 插入其中一台机器，你将能够获得满足以下条件的卡牌 $C$： - 如果你使用第一台机器，那么 $C$ 的强度等于 $A$ 和 $B$ 的强度中的最大值，并且 $C$ 的成本等于 $A$ 和 $B$ 的成本中的最大值。 - 如果你使用第二台机器，那么 $C$ 的强度等于 $A$ 和 $B$ 的强度中的最小值，并且 $C$ 的成本等于 $A$ 和 $B$ 的成本中的最小值。 JOI 君计划使用这些机器正好 $N - 1$ 次以获得一张新卡牌。为此，他将 $N$ 张卡牌按卡牌 $1$ 到卡牌 $N$ 的顺序依次排列。然后，他重复以下操作 $N - 1$ 次： - 选择两张相邻的卡牌，使用其中一台机器来得到一张新卡牌，并将新卡牌放在操作前所选两张卡牌的位置。在执行 $N-1$ 次操作后，JOI 君将只剩下一张卡牌。这张卡牌的强度和成本将取决于他执行的操作。 JOI 君有一个希望在执行 $N-1$ 次操作后获得的卡牌列表。第 $j$ 张卡牌（$1 \leq j \leq M$）由一对整数 $(T_j, W_j)$ 表示，其中 $T_j$ 是第 $j$ 张卡牌的强度，$W_j$ 是第 $j$ 张卡牌的成本。编写一个程序，给定有关 JOI 君卡牌的信息以及他想获得的卡牌列表，确定在执行 $N-1$ 次操作后他可以获得的列表中的哪些卡牌。 ## 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$ ## Output 向标准输出写入一行，输出应按升序包含 JOI 君可以在执行 $N-1$ 次操作后获得的列表中所有卡牌的编号。 [samples] ## Note #### 样例解释 1 例如，JOI 君可以通过以下方式获得一张强度为 2，成本为 3 的卡牌： - 交出卡牌 4 和卡牌 5，获得一张强度为 1，成本为 1 的卡牌。 - 交出卡牌 3 和第一次操作中获得的卡牌，获得一张强度为 1，成本为 1 的卡牌。 - 交出卡牌 1 和卡牌 2，获得一张强度为 2，成本为 3 的卡牌。 - 交出第二次和第三次操作中获得的卡牌，获得一张强度为 2，成本为 3 的卡牌。请注意，即使在第三次操作中获得了一张强度为 2，成本为 3 的卡牌，JOI 君仍需要执行最后一次操作。即使在某些操作后获得了某张卡牌，也可能在执行 $N-1$ 次操作后无法获得它。这个样例输入满足所有子任务的约束条件。 #### 样例解释 2 与此样例输出一样，如果在执行 $N-1$ 次操作后无法获得列表中的任何卡牌，则应输出一个空行。这个样例输入满足所有子任务的约束条件。 #### 样例解释 3 这个样例输入满足所有子任务的约束条件。 ### 约束条件 - $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$)． - 给定的值均为整数。 ### 子任务 1. (11 分) $N \leq 20$，$M \leq 10$． 2. (38 分) $N \leq 2,000$，$M \leq 10$． 3. (22 分) $M \leq 10$． 4. (29 分) 无额外约束。

Samples

Input #1

Output #1

1 3

Input #2

Output #2

Input #3

Output #3

3 4 5 8

API Response (JSON)

{
  "problem": {
    "name": "[JOIST 2024] 卡牌收集 / Card Collection",
    "description": {
      "content": "JOI 君对一款卡牌游戏中的卡牌收集充满热情。卡牌游戏中的每张卡牌都有两个整数，代表其强度和成本。为了获得一张新卡牌，JOI 君将 $N$ 张卡牌带到一个卡牌交换处。每张卡牌编号从 $1$ 到 $N$。第 $i$ 张卡牌（$1 \\leq i \\leq N$）的强度是 $S_i$，成本是 $V_i$。 卡牌交换处有两台机器可供使用。如果你将两张卡牌 $A$ 和 $B$ 插入其中一台机器，你将能够获",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10436"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "JOI 君对一款卡牌游戏中的卡牌收集充满热情。卡牌游戏中的每张卡牌都有两个整数，代表其强度和成本。为了获得一张新卡牌，JOI 君将 $N$ 张卡牌带到一个卡牌交换处。每张卡牌编号从 $1$ 到 $N$。第 $i$ 张卡牌（$1 \\leq i \\leq N$）的强度是 $S_i$，成本是 $V_i$。\n\n卡牌交换处有两台机器可供使用。如果你将两张卡牌 $A$ 和 $B$ 插入其中一台机器，你将能够获...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments