[JOIST 2023] 护照 / Passport

Luogu

IDLGP9331

Time2000ms

Memory1024MB

DifficultyP6

线段树2023O2优化最短路JOISC/JOIST（日本）

护照是旅行家进入他国时使用的证件。在一个星球上有 $N$ 个国家，从 $1$ 到 $N$ 编号。每个国家都签发一种护照。当旅行家获得由国家$i \ (1 \le i \le N)$ 签发的护照后，他能够进入国家 $L_i, L_i + 1, \dots, R_i$。**这里保证旅行家能够进入其签证的签发国。形式上地说, $L_i \le i \le R_i$ 必然成立。** 你有一个爱旅行的朋友。即使他奢望能环游世界，但他最初一种护照也没有。因此，他想通过一下重复以下两项行为来环游这 $N$ 个国家。 - 获得他当前所在国家签发的护照。 - 用他现有的护照进入某个国家。知道他的计划后，你想知道这个计划的是否可行，和如果可行的话，他最少需要的护照数量。因为你并不清楚他现在身处何国，所以你预测了 $Q$ 个他可能正居住在那的国家 $X_1, X_2, \dots, X_Q$。现在给定各国护照的信息 $L_i, R_i$ 和他可能居住的 $Q$ 个国家，您需要写一个程序，对于每一个可能居住的国家，判断他是否可能环游这 $N$ 个国家，如果可能的话，计算出他需要的最少护照种数。 ## Input 从标准输入读入： > $N$ > > $L_1 \ R_1$ > > $L_2 \ R_2$ > > $\vdots$ > > $L_N \ R_N$ > > $Q$ > > $X_1$ > > $X_2$ > > $\vdots$ > > $X_Q$ ## Output 输出 $Q$ 行至标准输出，第 $j \ (1 \le j \le Q)$ 行一个整数代表若你的朋友位于国家 $X_j$ 的答案。若他能环游这 $N$ 个国家，则输出他需要的最少护照种数，否则输出 $-1$。 [samples] ## Note **【数据范围】** 对于所有测试数据，满足 $2 \le N \le 2 \times 10 ^ 5$，$1 \le L_i \le i \le R_i \le N$，$1 \le Q \le N$，$1 \le X_1 < X_2 < \dots < X_Q \le N$，保证所有输入均为整数。 |子任务编号|分值|限制| |:-:|:-:|:-:| |$1$|$6$|$Q = 1$，$X_1 = 1$| |$2$|$16$|$N \le 300$，$Q = 1$| |$3$|$24$|$N \le 2500$，$Q = 1$| |$4$|$8$|$N \le 2500$| |$5$|$46$|无| **【样例解释 #1】** 假设你的朋友居住在国家 $X_1 = 1$，一种可行的方式如下，最后他获得了 $2$ 种护照： 1. 获得国家 $1$ 签发的护照。 2. 用国家 $1$ 签发的护照去国家 $2$ 旅行。 3. 获得国家 $2$ 签发的护照。 4. 用国家 $1$ 签发的护照去国家 $3$ 旅行。 5. 用国家 $2$ 签发的护照去国家 $4$ 旅行。可以证明不存在使用护照种数更小的方案，故输出 $2$。该样例满足所有子任务的限制。 **【样例解释 #2】** 假设你的朋友居住在国家 $X_1 = 3$。一种可行的方式如下，最后他获得了 $4$ 种护照： 1. 获得国家 $3$ 签发的护照。 2. 用国家 $3$ 签发的护照去国家 $2$ 旅行。 3. 获得国家 $2$ 签发的护照。 4. 用国家 $2$ 签发的护照去国家 $4$ 旅行。 5. 获得国家 $4$ 签发的护照。 6. 用国家 $4$ 签发的护照去国家 $5$ 旅行。 7. 获得国家 $5$ 签发的护照。 8. 用国家 $5$ 签发的护照去国家 $1$ 旅行。可以证明不存在使用护照种数更小的方案，故输出 $4$。该样例满足子任务 $2 \sim 5$ 的限制。 **【样例解释 #3】** 例如，如果你的朋友居住在 $X_3 = 3$，一种可行的方案书获得国家 $3$ 签发的护照，并用它来依次去国家 $1, 2, 4, 5$ 旅行。故第三行输出 $3$。但如果你的朋友居住在国家 $X_5 = 5$，即使他获得了国家 $5$ 签发的护照，他也不可能进入任何其他国家，因此，他无法实现自己的旅行计划。故第五行输出 $-1$。该样例满足子任务 $4 \sim 5$ 的限制。 **【样例解释 #4】** 该样例满足子任务 $4 \sim 5$ 的限制。

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

Input #4

Output #4

-1
-1
-1
-1

API Response (JSON)

{
  "problem": {
    "name": "[JOIST 2023] 护照 / Passport",
    "description": {
      "content": "护照是旅行家进入他国时使用的证件。 在一个星球上有 $N$ 个国家，从 $1$ 到 $N$ 编号。每个国家都签发一种护照。当旅行家获得由国家$i \\ (1 \\le i \\le N)$ 签发的护照后，他能够进入国家 $L_i, L_i + 1, \\dots, R_i$。**这里保证旅行家能够进入其签证的签发国。形式上地说, $L_i \\le i \\le R_i$ 必然成立。** 你有一个爱旅行的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9331"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "护照是旅行家进入他国时使用的证件。\n\n在一个星球上有 $N$ 个国家，从 $1$ 到 $N$ 编号。每个国家都签发一种护照。当旅行家获得由国家$i \\ (1 \\le i \\le N)$ 签发的护照后，他能够进入国家 $L_i, L_i + 1, \\dots, R_i$。**这里保证旅行家能够进入其签证的签发国。形式上地说, $L_i \\le i \\le R_i$ 必然成立。**\n\n你有一个爱旅行的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments