{"problem":{"name":"[JOI 2024 Final] 马拉松比赛 2 / Marathon Race 2","description":{"content":"JOI 大道是一条东西向的长度为 $L$ 米的道路，地点 $l$ 位于从道路的西端走 $l\\ (0 \\leq l \\leq L)$ 米的地方。 今年 JOI 大道上第一次举办了马拉松大会。这个马拉松大会的规则和一般的不同，是按照以下的方式进行的： - 道路上放了 $N$ 个球，第 $i\\ (1 \\leq i \\leq N)$ 个球放在地点 $X_{i}$。有些地方可能有多个球放在一起。 - 参","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10207"},"statements":[{"statement_type":"Markdown","content":"JOI 大道是一条东西向的长度为 $L$ 米的道路，地点 $l$ 位于从道路的西端走 $l\\ (0 \\leq l \\leq L)$ 米的地方。\n\n今年 JOI 大道上第一次举办了马拉松大会。这个马拉松大会的规则和一般的不同，是按照以下的方式进行的：\n\n- 道路上放了 $N$ 个球，第 $i\\ (1 \\leq i \\leq N)$ 个球放在地点 $X_{i}$。有些地方可能有多个球放在一起。\n- 参加者从规定的起点出发，拿到所有 $N$ 个球后，如果在规定的时间内到达规定的终点，就算是完赛。但是，如果把拿到的球放在地上就会被取消资格。\n\n这个大会的起点，终点和时间限制还没有公布，但是已经公布了 $Q$ 个可能的方案。第 $j\\ (1 \\leq j \\leq Q)$ 个方案的起点是地点 $S_{j}$，终点是地点 $G_{j}$，时间限制是 $T_{j}$ 秒。\n\n理恵是马拉松大会的其中一名运动员。她拿起一个球要花 $1$ 秒，拿着 $x$ 个球在道路上跑 $1$ 米要花 $x+1$ 秒。\n\n给出 JOI 大道，球，方案的信息。编写一个程序，对于每个方案判断理恵能不能完赛。\n\n## Input\n\n第一行包含两个整数 $N,L$。\n\n第二行包含用空格分隔的 $N$ 个整数 $X_1, X_2, \\ldots ,X_N$。\n\n第三行包含一个整数 $Q$。\n\n接下来 $Q$ 行，每行包含三个整数 $S_j, G_j, T_j$，表示第 $j$ 个方案。\n\n## Output\n\n输出 $Q$ 行。第 $j\\ (1 \\leq j \\leq Q)$ 行，如果第 $j$ 个方案理恵能完赛输出 Yes，否则输出 No。\n\n[samples]\n\n## Note\n\n对于所有输入数据，满足：\n\n- $1 \\leq N \\leq 5\\times 10^5$\n- $1 \\leq L \\leq 5\\times 10^5$\n- $0 \\leq X_{i} \\leq L\\ (1 \\leq i \\leq N)$\n- $1 \\leq Q \\leq 5\\times 10^5$\n- $0 \\leq S_{j} \\leq L\\ (1 \\leq j \\leq Q)$\n- $0 \\leq G_{j} \\leq L\\ (1 \\leq j \\leq Q)$\n- $1 \\leq T_{j} \\leq 5\\times 10^5\\ (1 \\leq j \\leq Q)$\n\n详细子任务附加限制及分值如下表所示。\n\n|子任务|\t附加限制|\t分值|\n|:-:|:-:|:-:|\n|1|\t$N \\leq 7, Q \\leq 10, S_{j}=0, G_{j}=0\\ (1 \\leq j \\leq Q)$|\t7\n|2|\t$N \\leq 7, Q \\leq 10$|\t7\n|3|\t$N \\leq 14, Q \\leq 10$|\t10\n|4|\t$N \\leq 100, Q \\leq 10$|\t28\n|5|\t$N \\leq 2000, Q \\leq 10$|\t10\n|6|\t$N \\leq 2000$|\t19\n|7|\t无附加限制\t|19","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10207","tags":["动态规划 DP","2024","JOI（日本）"],"sample_group":[["3 100\n30 80 30\n3\n0 100 403\n0 100 300\n0 100 262","Yes\nYes\nNo"],["3 100\n30 80 30\n3\n0 0 403\n0 0 300\n0 0 262","Yes\nNo\nNo"],["6 100\n0 50 100 0 50 100\n4\n20 70 600\n70 20 600\n10 40 600\n40 10 600","No\nYes\nNo\nYes"]],"created_at":"2026-03-03 11:09:25"}}