配点: 100 点
問題文
JOI路足够长,可以从东延伸到西 L 距离道路西端米。 l 米(0 \leqq l \leqq L) 你前进的地方是一个点 它被称为 l 。
今年,JOI凯多将首次举办马拉松赛事。本次马拉松赛事与一般规则不同,将按照以下规则进行。
- 在路上 N 球被放置,i 番目 (1 \leqq i \leqq N) 球位于该点 它位于 X_i 。多个球可以放置在同一位置。
- 参赛者从指定起点出发。 如果您在时限内带着所有
- N 球到达指定的球门点,完走变为。然而,如果你把球放在地上,你将被取消资格。
本次比赛的起点、终点和时限尚未公布,但 已经宣布将发生Q 场景之一。 j 番目 (1 \leqq j \leqq Q)场景,起点是 S_j,目标点就是点 G_j,时间限制 T_j 秒。
马拉松比赛的参与者 Rie 拿着一个球。 1 捡起碎片 需要 1 秒, 手里拿着x 球走在路上 1 运行仪表 需要 x+1 秒。
JOI 给定有关道路、球和场景的信息,编写一个程序来确定 Rie 是否有办法完成每个场景的比赛。
入力
输入是按以下格式从标准输入给出的。
N L X_1 X_2 \cdots X_N Q S_1 G_1 T_1 S_2 G_2 T_2 \vdots S_Q G_Q T_Q
出力
到标准输出 Q 输出在一行。
j 行目 (1 \leqq j \leqq Q)有
如果理惠有办法在第j 场景中完成比赛 Yes,否则
输出 No 。
在第
制約
- 1 \leqq N \leqq 500\,000.
- 1 \leqq L \leqq 500\,000.
- 0 \leqq X_i \leqq L (1 \leqq i \leqq N).
- 1 \leqq Q \leqq 500\,000.
- 0 \leqq S_j \leqq L (1 \leqq j \leqq Q).
- 0 \leqq G_j \leqq L (1 \leqq j \leqq Q).
- 1 \leqq T_j \leqq 500\,000 (1 \leqq j \leqq Q).
- 所有输入值都是整数。
小課題
- (7 点) N \leqq 7,Q \leqq 10,S_j = 0,G_j = 0 (1 \leqq j \leqq Q).
- (7 点) N \leqq 7,Q \leqq 10.
- (10 点) N \leqq 14,Q \leqq 10.
- (28 点) N \leqq 100,Q \leqq 10.
- (10 点) N \leqq 2\,000,Q \leqq 10.
- (19 点) N \leqq 2\,000.
- (19 点)没有额外的限制。
入力例 1
3 100 30 80 30 3 0 100 403 0 100 300 0 100 262
出力例 1
Yes Yes No
1 场景中,起点是 0、目标点就是点 100、时限为 403 秒。如下图所示,
您可以在 263 秒内完成比赛。因此,
从1 行是 Yes 。
| 順番 | 行動 | 消費時間 | 累計時間 |
|---|---|---|---|
| 1 | 地点 0 开始,点 拿起第 30 。 | 30 秒 | 30 秒 |
| 2 | 1 个球。 | 1 秒 | 31 秒 |
| 3 | 3 个球。 | 1 秒 | 32 秒 |
| 4 | 地点 30 点 移动到 80 。 | 150 秒 | 182 秒 |
| 5 | 2 个球。 | 1 秒 | 183 秒 |
| 6 | 地点 80 点 移动到 100 并完成比赛。 在第 | 80 秒 | 263 秒 |
2 场景中,起点和终点是
与第 1 场景相同,但时间限制为 300 秒。方法和之前一样,在限定时间内 263 秒内完成比赛。因此,
从2 行是 Yes 。
3 场景中,起点和终点是
与第 1, 2 场景相同,但时间限制为 262 秒。没有办法在限定时间内完成比赛。因此,3 行是 No 。
此输入示例是一个小作业。 满足 2, 3, 4, 5, 6, 7 满足约束。 与
入力例 2
3 100 30 80 30 3 0 0 403 0 0 300 0 0 262
出力例 2
Yes No No
1 场景中,起点是 0、目标点就是点 0、时限为 403 秒。如下图所示,
您可以在 403 秒内完成比赛。因此,
从1 行是 Yes 。
| 順番 | 行動 | 消費時間 | 累計時間 |
|---|---|---|---|
| 1 | 地点 0 开始,点 拿起第 30 。 | 30 秒 | 30 秒 |
| 2 | 1 个球。 | 1 秒 | 31 秒 |
| 3 | 地点 30 点 移动到 80 。 | 100 秒 | 131 秒 |
| 4 | 2 个球。 | 1 秒 | 132 秒 |
| 5 | 地点 80 点 移动到 30 。 | 150 秒 | 282 秒 |
| 6 | 3 个球。 | 1 秒 | 283 秒 |
| 7 | 地点 30 点 移动到 0 并完成比赛。 在第 | 120 秒 | 403 秒 |
2, 3 场景中,起点和终点是
与第 1 场景相同,但时间限制为 300 秒,262 秒。无论哪种情况,都无法在限定时间内完成比赛。因此,2 行是 No ,3 行是 No 。
此输入示例是一个小作业。 满足 1, 2, 3, 4, 5, 6, 7 满足约束。 与
入力例 3
6 100 0 50 100 0 50 100 4 20 70 600 70 20 600 10 40 600 40 10 600
出力例 3
No Yes No Yes
此输入示例是一个小作业。 满足 2, 3, 4, 5, 6, 7 满足约束。 与