2024-ho-t3_Marathon_Race_2 — JOI JOI
Task type: batch | Time limit: 1.5 s | Memory limit: 1024 MB | Difficulty: 21
Algorithms: ad-hoc, dynamic programming

![](_page_0_Picture_0.jpeg)

![](_page_0_Picture_2.jpeg)

# 3. Marathon Race 2

The 23rd Japanese Olympiad in Informatics (JOI 2023/2024)
Final Round
February 4, 2024 (Online)

JOI Avenue is a road of length *L* in an east-west direction. The place of *l* meters (0 ≤ *l* ≤ *L*) from the west end on the road is called "position *l*".

The first marathon race in JOI Avenue is going to be held this year. The race has a different regulation from normal one, which is described in the following:

*   Before the race, *N* balls are located on the road. The *i*-th ball (1 ≤ *i* ≤ *N*) is located at position *X<sub>i</sub>*. Multiple balls may be located at the same position.
*   The participant starts at the designated position.
*   The participant collects all *N* balls and finishes at the designated position. When this is achieved within the designated time limit, one completes the race. However, once the participant collects a ball, they must not put the ball on the road, otherwise they will be disqualified from the race.

The starting and finishing position, and the time limit, are not yet announced, but it is known that they are chosen from *Q* scenarios. The *j*-th scenario (1 ≤ *j* ≤ *Q*) is that the participant starts at position *S<sub>j</sub>*, finishes at position *G<sub>j</sub>*, and the time limit is *T<sub>j</sub>* seconds.

Rie is participating in the marathon race. She spends 1 second to collect 1 ball. She spends *x* + 1 seconds to move 1 meter, where *x* is the number of balls she is carrying.

Write a program which, given the information of JOI Avenue, the positions of balls, and the scenarios, determines whether there exists a way for Rie to complete the race for each scenario.

## Input

Read the following data from the standard input.

```
N L
X1 X2 ... XN
Q
S1 G1 T1
S2 G2 T2
...
SQ GQ TQ
```

## Output

Write *Q* lines to the standard output. On the *j*-th line (1 ≤ *j* ≤ *Q*), output `Yes` if there exists a way for Rie to complete the race for scenario *j*, and `No` otherwise.

## Constraints

*   1 ≤ *N* ≤ 500 000.
*   1 ≤ *L* ≤ 500 000.
*   0 ≤ *X<sub>i</sub>* ≤ *L* (1 ≤ *i* ≤ *N*).
*   1 ≤ *Q* ≤ 500 000.
*   0 ≤ *S<sub>j</sub>* ≤ *L* (1 ≤ *j* ≤ *Q*).
*   0 ≤ *G<sub>j</sub>* ≤ *L* (1 ≤ *j* ≤ *Q*).
*   1 ≤ *T<sub>j</sub>* ≤ 500 000 (1 ≤ *j* ≤ *Q*).
*   Given values are all integers.

## Subtasks

1.  (7 points) *N* ≤ 7, *Q* ≤ 10, *S<sub>j</sub>* = 0, *G<sub>j</sub>* = 0 (1 ≤ *j* ≤ *Q*).
2.  (7 points) *N* ≤ 7, *Q* ≤ 10.
3.  (10 points) *N* ≤ 14, *Q* ≤ 10.
4.  (28 points) *N* ≤ 100, *Q* ≤ 10.
5.  (10 points) *N* ≤ 2 000, *Q* ≤ 10.
6.  (19 points) *N* ≤ 2 000.
7.  (19 points) No additional constraints.

## Sample Input and Output

| Sample Input    | Sample Output | Explanation                                                                                                                                                                                                                                                                                                            |
|-----------------|---------------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `3 100`         | `Yes`         | In the 1st scenario, the participant starts at position 0, finishes at position 100, and the time limit is 403 seconds. Rie can complete the race in 263 seconds, which is within the time limit, in the following way. Therefore, output Yes in the 1st line.                                                  |
| `30 80 30`      | `Yes`         |                                                                                                                                                                                                                                                                                                                      |
| `3`             | `No`          |                                                                                                                                                                                                                                                                                                                      |
| `0 100 403`     |               |                                                                                                                                                                                                                                                                                                                      |
| `0 100 300`     |               |                                                                                                                                                                                                                                                                                                                      |
| `0 100 262`     |               |                                                                                                                                                                                                                                                                                                                      |
|                 |               |                                                                                                                                                                                                                                                                                                                      |
| Order | Action                                                        | Time (sec.) | Total Time (sec.) |
|-------|---------------------------------------------------------------|-------------|-------------------|
| 1     | Start at position 0 and move to position 30.                  | 30          | 30                |
| 2     | Collect the 1st ball.                                         | 1           | 31                |
| 3     | Collect the 3rd ball.                                         | 1           | 32                |
| 4     | Move from position 30 to position 80.                         | 150         | 182               |
| 5     | Collect the 2nd ball.                                         | 1           | 183               |
| 6     | Move from position 80 to position 100, and complete the race. | 80          | 263               |
|                 |               | In the 2nd scenario, the starting and finishing position is the same as the 1st scenario, but the time limit is 300 seconds. Rie can complete the race in 263 seconds, which is within the time limit, in the same way as above. Therefore, output Yes in the 2nd line.                                        |
|                 |               | In the 3rd scenario, the starting and finishing position is the same as the 1st and the 2nd scenarios, but the time limit is 262 seconds. There does not exist a way for Rie to complete the race within the time limit. Therefore, output No in the 3rd line.                                                |
|                 |               | This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6, 7.                                                                                                                                                                                                                                      |
| `3 100`         | `Yes`         | In the 1st scenario, the participant starts at position 0, finishes at position 0, and the time limit is 403 seconds. Rie can complete the race in 403 seconds, which is within the time limit, in the following way. Therefore, output Yes in the 1st line.                                                   |
| `30 80 30`      | `No`          |                                                                                                                                                                                                                                                                                                                      |
| `3`             | `No`          |                                                                                                                                                                                                                                                                                                                      |
| `0 0 403`       |               |                                                                                                                                                                                                                                                                                                                      |
| `0 0 300`       |               |                                                                                                                                                                                                                                                                                                                      |
| `0 0 262`       |               |                                                                                                                                                                                                                                                                                                                      |
|                 |               | Order | Action                                                      | Time (sec.) | Total Time (sec.) |
|-------|-------------------------------------------------------------|-------------|-------------------|
| 1     | Start at position 0 and move to position 30.                | 30          | 30                |
| 2     | Collect the 1st ball.                                       | 1           | 31                |
| 3     | Move from position 30 to position 80.                       | 100         | 131               |
| 4     | Collect the 2nd ball.                                       | 1           | 132               |
| 5     | Move from position 80 to position 30.                       | 150         | 282               |
| 6     | Collect the 3rd ball.                                       | 1           | 283               |
| 7     | Move from position 30 to position 0, and complete the race. | 120         | 403               |
|                 |               | In the 2nd and the 3rd scenarios, the starting and finishing position is the same as the 1st scenario, but the time limit is 300 seconds and 262 seconds, respectively. There does not exist a way for Rie to complete the race within the time limit, for both scenarios. Therefore, output No in the 2nd and the 3rd line.|
|                 |               | This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 5, 6, 7.                                                                                                                                                                                                                                      |
| `6 100`         | `No`          |                                                                                                                                                                                                                                                                                                                      |
| `0 50 100 0 50 100`| `Yes`         |                                                                                                                                                                                                                                                                                                                      |
| `4`             | `No`          |                                                                                                                                                                                                                                                                                                                      |
| `20 70 600`     | `Yes`         |                                                                                                                                                                                                                                                                                                                      |
| `70 20 600`     |               |                                                                                                                                                                                                                                                                                                                      |
| `10 40 600`     |               |                                                                                                                                                                                                                                                                                                                      |
| `40 10 600`     |               |                                                                                                                                                                                                                                                                                                                      |
|                 |               | This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6, 7.                                                                                                                                                                                                                                      |

Starter code: