分数: 100 点
问题陈述
玻利维亚首都拉巴斯以旅游胜地和名为 Mi Teleférico 的空中缆车而闻名。您现在来拉巴斯观光,并且想要参观尽可能多的观光景点。在此任务中,我们考虑以下简化情况。
有 N 拉巴斯空中缆车站,编号为 1 to N 按海拔升序排列。 M 单向 行,编号自 1 to M。有 P 空中缆车公司,编号自 1 to P。每条生产线均由一家公司管理。线 i (1 \leq i \leq M) 从车站操作 A_i 到车站 B_i,由公司管理 C_i。在这里,线路总是从海拔较低的车站运行到海拔较高的车站。换句话说, A_i < B_i 成立。
拉巴斯交通局为方便起见发放了无限次乘车通行证。每张乘车通行证包含 2 整数 l, r,满足 1 \leq l \leq r \leq P。通行证使持有者能够乘坐由任何一家公司管理的线路 l, l + 1, \dots, r。换句话说,对于一个整数 i 满足 1 \leq i \leq M,通行证使持有者可以乘坐线路 i 当 l \leq C_i \leq r 成立。可以对多条线路使用一次通道。让一趟车过去 (l, r) 表示此乘车卡。
现在, Q 游客,编号自 1 to Q,访问拉巴斯。游客 j (1 \leq j \leq Q) 有乘车通行证 (L_j, R_j) 和 X_j 玻利维亚现金。
每个游客的目标是确保没有一站不能出行 1,仅使用可以使用他或她拥有的乘车通行证乘坐的路线。游客 j (1 \leq j \leq Q)可以按照以下流程交换他或她的乘车通行证来实现他们的目标。在这里,每个游客最多只能兑换一次。
- 他或她选择 2 整数 l', r',满足 1 \leq l' \leq r' \leq P.
- 他或她交换乘车通行证 (L_j, R_j) 乘车通行证 (l', r').它的成本 |L_j - l'| + |R_j - r'| 玻利维亚诺作为费用。
您的目的是确定每位游客是否可以在其拥有的现金范围内实现其目标。
编写一个程序,根据有关车站、线路和游客的信息,确定他或她是否可以在每个游客拥有的现金范围内实现他或她的目标。
输入
从标准输入读取以下数据。
N M P A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M Q L_1 R_1 X_1 L_2 R_2 X_2 \vdots L_Q R_Q X_Q
输出
写 Q 行到标准输出。 j- 第行 (1 \leq j \leq Q),输出 Yes 如果游客 j 能够实现他或她的目标,并且 No 否则。
约束
- 2 \leq N \leq 300\,000.
- 1 \leq M \leq 300\,000.
- 1 \leq P \leq 10^9.
- 1 \leq A_i < B_i \leq N (1 \leq i \leq M).
- 1 \leq C_i \leq P (1 \leq i \leq M).
- 1 \leq Q \leq 400\,000.
- 1 \leq L_j \leq R_j \leq P (1 \leq j \leq Q).
- 0 \leq X_j \leq 10^9 (1 \leq j \leq Q).
- 给定值均为整数。
子任务
- (7 点) N \leq 50, M \leq 50, Q \leq 50, X_j = 0 (1 \leq j \leq Q).
- (8 点) P \leq 10.
- (11 点) P \leq 100.
- (23 点) P \leq 300\,000, X_j = 0 (1 \leq j \leq Q).
- (9 点) P \leq 300\,000.
- (22 点) N \leq 8\,000, M \leq 8\,000.
- (20 点)没有额外的限制。
示例输入 1
4 6 10 1 2 3 2 4 7 1 2 6 2 3 5 3 4 2 3 4 8 4 3 7 0 5 6 0 3 4 0 1 9 0
示例输出 1
Yes No No Yes
一、旅游 1 有乘车通行证 (3, 7) 和 0 玻利维亚诺最初现金。他或她不需要交换就可以实现他或她的目标。因为,这张通行证可以让游客 1 骑行 4 线,线 1, 2, 3, 4,他或她可以从车站移动到每个车站 1 通过使用这些 4 行如下。
- 可以作为车站移动 1 \rightarrow 2 通过使用线 3.
- 可以作为车站移动 1 \rightarrow 2 \rightarrow 3 通过使用线条 1, 4 按此顺序。
- 可以作为车站移动 1 \rightarrow 2 \rightarrow 4 通过使用线条 3, 2 按此顺序。
因此,输出 Yes 上 1-st 行。
接下来,游客 2 有乘车通行证 (5, 6) 和 0 玻利维亚诺最初现金。然而,他或她无法实现他或她的目标。因为,这张通行证可以让游客 2 骑行 2 线,线 3, 4,并且他或她无法移动电台 4 从车站 1 通过使用这些 2 行。而且,由于旅游 2 只有 0 玻利维亚诺作为现金,他或她不能将通行证与其他通行证兑换。
因此,输出 No 上 2-nd 行。
另外,游客 3 无法实现他或她的目标,并且游客 4 可以实现他或她的目标。因此,输出 No 上 3-rd 行,并输出 Yes 上 4第行。
此示例输入满足所有子任务的约束。
示例输入 2
4 6 10 1 2 3 2 4 7 1 2 6 2 3 5 3 4 2 3 4 8 3 5 6 10 3 4 1 7 8 3
示例输出 2
Yes No Yes
车站和线路信息与示例输入相同 1.
一、旅游 1 有乘车通行证 (5, 6) 和 10 玻利维亚诺最初现金。他或她可以通过以下交换来实现他或她的目标。
- 他或她选择 2 整数 l' = 1, r' = 5,满足 1 \leq l' \leq r' \leq P.
- 他或她交换乘车通行证 (5, 6) 乘车通行证 (1, 5).它的成本 |5 - 1| + |6 - 5| = 5 玻利维亚诺作为费用。
因此,输出 Yes 上 1-st 行。
接下来,游客 2 有乘车通行证 (3, 4) 和 1 玻利维亚诺最初现金。他或她无法通过任何交换来实现他或她的目标。
检查,输出 No 上 2-nd 行。
自游客以来 3 可以实现他或她的目标,输出 Yes 上 3-rd 行。
此示例输入满足子任务的约束 2,3,5,6,7.
示例输入 3
3 1 1000000000 1 2 6 1 1 1000000000 1000000000
示例输出 3
No
无法从车站移动 1 到车站 3 有了这些线路,游客无论拥有何种乘车通行证都无法实现他们的目标。
此示例输入满足子任务的约束 6,7.
示例输入 4
5 9 2000 2 3 1814 2 3 457 1 2 1226 3 4 1354 1 5 1050 1 2 1725 2 3 1383 1 5 1626 1 4 1795 5 850 1872 128 82 428 1217 487 924 573 1639 1926 202 202 420 25
示例输出 4
Yes Yes Yes Yes No
此示例输入满足子任务的约束 5,6,7.