P10207 [JOI 2024 Final] Marathon Race 2

JOI Avenue is an east-west road with length $L$ meters. A location $l$ is the point that is $l\ (0 \leq l \leq L)$ meters from the west end of the road. This year, a marathon event is held on JOI Avenue for the first time. The rules of this marathon are different from usual, and it is run in the following way: - There are $N$ balls placed on the road. The $i\ (1 \leq i \leq N)$-th ball is placed at location $X_{i}$. There may be multiple balls placed at the same location. - A participant starts from the designated start point, collects all $N$ balls, and is considered to have finished if they reach the designated goal point within the designated time limit. However, if they put down any collected ball on the ground, they will be disqualified. The start point, goal point, and time limit of this event have not been announced yet, but $Q$ possible plans have been announced. In the $j\ (1 \leq j \leq Q)$-th plan, the start point is location $S_{j}$, the goal point is location $G_{j}$, and the time limit is $T_{j}$ seconds. Rie is one of the athletes in the marathon event. It takes her $1$ second to pick up one ball, and running $1$ meter on the road while carrying $x$ balls takes $x+1$ seconds. Given the information about JOI Avenue, the balls, and the plans, write a program to determine for each plan whether Rie can finish.

The first line contains two integers $N, L$. The second line contains $N$ integers $X_1, X_2, \ldots ,X_N$ separated by spaces. The third line contains one integer $Q$. The next $Q$ lines each contain three integers $S_j, G_j, T_j$, representing the $j$-th plan.

Output $Q$ lines. On the $j\ (1 \leq j \leq Q)$-th line, output `Yes` if Rie can finish in the $j$-th plan; otherwise output `No`.

For all input data, the following conditions are satisfied: - $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)$ The detailed additional constraints and scores for subtasks are shown in the table below. |Subtask|Additional Constraints|Score| |:-:|:-:|:-:| |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|No additional constraints.|19| Translated by ChatGPT 5