← 返回题目列表

AtCoder · joi2024ho_c

C. 马拉松比赛 2

中文机器翻译题面 查看原题

配点: 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).
  • 所有输入值都是整数。

小課題

  1. (7 点) N \leqq 7,Q \leqq 10,S_j = 0,G_j = 0 (1 \leqq j \leqq Q).
  2. (7 点) N \leqq 7,Q \leqq 10.
  3. (10 点) N \leqq 14,Q \leqq 10.
  4. (28 点) N \leqq 100,Q \leqq 10.
  5. (10 点) N \leqq 2\,000,Q \leqq 10.
  6. (19 点) N \leqq 2\,000.
  7. (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 满足约束。 与