[JOI 2024 Final] 马拉松比赛 2 / Marathon Race 2

Luogu

IDLGP10207

Time1500ms

Memory1024MB

DifficultyP6

动态规划 DP2024JOI（日本）

JOI 大道是一条东西向的长度为 $L$ 米的道路，地点 $l$ 位于从道路的西端走 $l\ (0 \leq l \leq 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$ 秒，拿着 $x$ 个球在道路上跑 $1$ 米要花 $x+1$ 秒。给出 JOI 大道，球，方案的信息。编写一个程序，对于每个方案判断理恵能不能完赛。 ## Input 第一行包含两个整数 $N,L$。第二行包含用空格分隔的 $N$ 个整数 $X_1, X_2, \ldots ,X_N$。第三行包含一个整数 $Q$。接下来 $Q$ 行，每行包含三个整数 $S_j, G_j, T_j$，表示第 $j$ 个方案。 ## Output 输出 $Q$ 行。第 $j\ (1 \leq j \leq Q)$ 行，如果第 $j$ 个方案理恵能完赛输出 Yes，否则输出 No。 [samples] ## Note 对于所有输入数据，满足： - $1 \leq N \leq 5\times 10^5$ - $1 \leq L \leq 5\times 10^5$ - $0 \leq X_{i} \leq L\ (1 \leq i \leq N)$ - $1 \leq Q \leq 5\times 10^5$ - $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 5\times 10^5\ (1 \leq j \leq Q)$ 详细子任务附加限制及分值如下表所示。 |子任务| 附加限制| 分值| |:-:|:-:|:-:| |1| $N \leq 7, Q \leq 10, S_{j}=0, G_{j}=0\ (1 \leq j \leq Q)$| 7 |2| $N \leq 7, Q \leq 10$| 7 |3| $N \leq 14, Q \leq 10$| 10 |4| $N \leq 100, Q \leq 10$| 28 |5| $N \leq 2000, Q \leq 10$| 10 |6| $N \leq 2000$| 19 |7| 无附加限制 |19

Samples

Input #1

Output #1

Yes
Yes
No

Input #2

Output #2

Yes
No
No

Input #3

6 100
0 50 100 0 50 100
4
20 70 600
70 20 600
10 40 600
40 10 600

Output #3

No
Yes
No
Yes

API Response (JSON)

{
  "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- 参...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments