AT_joi2024ho_c マラソン大会 2 (Marathon Race 2)

JOI 街道是一条东西方向延伸、长为 $L$ 米的道路。从道路西端起第 $l$ 米处称为地点 $l$。 今年，JOI 街道将首次举办马拉松比赛。与普通马拉松不同，本次比赛有如下规则： - 道路上放置了 $N$ 个球，第 $i$ 个球（$1 \leq i \leq N$）放在地点 $X_i$。多个球可能位于同一地点。 - 参赛者从指定的起点出发。 - 只有在到达指定的终点，并且收集了全部 $N$ 个球，并在限定时间内到达，才能算作**完赛**。但如果在持有球的情况下将球放下，则会被判定为失格。 本次比赛的起点、终点和限制时间尚未公布，但已知将会在 $Q$ 个场景中的某一个发生。第 $j$ 个场景（$1 \leq j \leq Q$）的起点为 $S_j$，终点为 $G_j$，限制时间为 $T_j$ 秒。 参赛者理惠拾起 $1$ 个球需要 $1$ 秒，携带 $x$ 个球在道路上跑 $1$ 米需要 $x+1$ 秒。 给定 JOI 街道、球和场景的相关信息，请编写程序，判断对于每个场景，理惠是否存在完赛的方法。

输入通过标准输入给出，格式如下： > $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 \leq j \leq Q$）若在第 $j$ 个场景下理惠存在完赛的方法，则输出 `Yes`，否则输出 `No`。

## 小子任务 1.（$7$ 分）$N \leq 7$，$Q \leq 10$，$S_j = 0$，$G_j = 0$（$1 \leq j \leq Q$）。 2.（$7$ 分）$N \leq 7$，$Q \leq 10$。 3.（$10$ 分）$N \leq 14$，$Q \leq 10$。 4.（$28$ 分）$N \leq 100$，$Q \leq 10$。 5.（$10$ 分）$N \leq 2\,000$，$Q \leq 10$。 6.（$19$ 分）$N \leq 2\,000$。 7.（$19$ 分）无附加限制。 --- ## 样例解释 1 在第 $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$ 个场景中，起点和终点与前两个场景相同，但限制时间为 $262$ 秒，无法在限制时间内完赛。因此第 $3$ 行输出 `No`。 此输入样例满足小子任务 $2, 3, 4, 5, 6, 7$ 的限制。 --- ## 样例解释 2 在第 $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 此输入样例满足小子任务 $2, 3, 4, 5, 6, 7$ 的限制。 ## 数据范围与约定 - $1 \leq N \leq 500\,000$。 - $1 \leq L \leq 500\,000$。 - $0 \leq X_i \leq L$（$1 \leq i \leq N$）。 - $1 \leq Q \leq 500\,000$。 - $0 \leq S_j \leq L$（$1 \leq j \leq Q$）。 - $0 \leq G_j \leq L$（$1 \leq j \leq Q$）。 - $1 \leq T_j \leq 500\,000$（$1 \leq j \leq Q$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译