#P6431. 「JOISC 2023 Day1」护照

    ID: 5920 传统题 2000ms 1024MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>难度分类省选/NOI-构造与建模不变量分析图论拆点线段树优化建图反图求到终点距离Dijkstra超级源汇CF2600

「JOISC 2023 Day1」护照

「JOISC 2023 Day1」护照

题目描述

护照是旅行者进入外国时在世界范围内使用的一种证件。

在一颗星球上有 NN 个国家,从 11 到 NN 编号。每个国家签发一种护照。当旅行者持有国家 i (1≤i≤N)i\ (1\le i\le N) 签发的护照时,他可以进入国家 Li,Li+1,…,RiL_i,L_i+1,\ldots,R_i。这里,保证旅行者可以进入所持护照的签发国。也就是说,保证 Li≤i≤RiL_i\le i\le R_i。

你有一个喜欢旅行的朋友。他梦想环游世界,但他最开始没有护照。因此,他计划通过重复如下两个操作来环游所有的 NN 个国家。

  • 他获得了他目前所在国家签发的护照
  • 他移动到一个可以使用他目前拥有的护照入境的国家

当你听说了他的计划时,你想知道他是否可以实现他的计划,并且如果可以的话,他至少需要获得多少本护照。因为你不知道他住在哪儿,你假设他住在 QQ 个可能的国家 X1,X2,…,XQX_1,X_2,\ldots,X_Q。

给定护照和他可能居住的国家,写一个程序计算对于所有可能,他是否能够环游所有 NN 个国家,并且如果可能的话,计算他至少要获得多少本护照。

已经取得的护照会一直保留,进入国家时只需持有的任意一本护照允许入境即可;取得新护照不会替换旧护照。可以重复到访国家,初始所在国已经算作到访。各个起点的询问互相独立,每次都从没有护照的状态开始。

输入格式

第一行一个整数 NN。

接下来 NN 行,每行两个整数 Li,RiL_i,R_i。

接下来一行一个整数 QQ。

接下来 QQ 行,每行一个整数 XjX_j。

输出格式

输出 QQ 行,对于第 jj 行输出你的朋友住在国家 XjX_j 的情况的答案。如果他可以环游所有 NN 个国家,输出他最少获得护照本数。否则输出 −1-1。

样例输入 1

4
1 3
2 4
2 3
4 4
1
1

样例输出 1

2

样例输入 2

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

样例输出 2

4

样例输入 3

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

样例输出 3

-1
2
1
2
-1

样例输入 4

4
1 2
1 2
3 4
3 4
4
1
2
3
4

样例输出 4

-1
-1
-1
-1

样例说明

样例 1:在国家 11 取得其护照,前往国家 22 并取得国家 22 的护照,再使用国家 11 的护照前往国家 33,最后使用国家 22 的护照前往国家 44。共需两本护照。

样例 2:从国家 33 出发,可以依次在国家 3,2,4,53,2,4,5 取得护照,并依次前往 2,4,5,12,4,5,1,共需四本。样例 3 中,从国家 33 出发只需一本本国护照就能去所有国家;从国家 55 出发则无法进入其他国家。

数据范围与提示

对于所有输入数据,满足:

  • 2≤N≤2×1052\le N\le 2\times 10^5
  • 1≤Li≤i≤Ri≤N1\le L_i\le i\le R_i\le N
  • 1≤Q≤N1\le Q\le N
  • 1≤Xj≤N (1≤j≤Q)1\le X_j\le N\ (1\le j\le Q),Xj<Xj+1 (1≤j<Q)X_j<X_{j+1}\ (1\le j<Q)

详细子任务附加限制及分值如下表所示。

子任务编号 附加限制 分值
11 Q=1,X1=1Q=1,X_1=1 66
22 N≤300,Q=1N\le 300,Q=1 1616
33 N≤2 500,Q=1N\le 2\ 500,Q=1 2424
44 N≤2 500N\le 2\ 500 88
55 无附加限制 4646