| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 129 | 38 | 33 | 29.730% |
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:
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_j,ドル finishes at position $G_j,ドル and the time limit is $T_j$ 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.
Read the following data from the standard input.
$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$
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.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $N ≤ 7,ドル $Q ≤ 10,ドル $S_j = 0,ドル $G_j = 0$ (1ドル ≤ j ≤ Q$). |
| 2 | 7 | $N ≤ 7,ドル $Q ≤ 10$. |
| 3 | 10 | $N ≤ 14,ドル $Q ≤ 10$. |
| 4 | 28 | $N ≤ 100,ドル $Q ≤ 10$. |
| 5 | 10 | $N ≤ 2,円 000,ドル $Q ≤ 10$. |
| 6 | 19 | $N ≤ 2,円 000$. |
| 7 | 19 | No additional constraints. |
3 100 30 80 30 3 0 100 403 0 100 300 0 100 262
Yes Yes No
In the 1ドル$st 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 1ドル$st line.
| Order | Action | Time (sec.) | Total Time (sec.) |
|---|---|---|---|
| 1 | Start at position 0ドル$ and move to position 30ドル$. | 30ドル$ | 30ドル$ |
| 2 | Collect the 1ドル$st ball. | 1ドル$ | 31ドル$ |
| 3 | Collect the 3ドル$rd ball. | 1ドル$ | 32ドル$ |
| 4 | Move from position 30ドル$ to position 80ドル$. | 150ドル$ | 182ドル$ |
| 5 | Collect the 2ドル$nd ball. | 1ドル$ | 183ドル$ |
| 6 | Move from position 80ドル$ to position 100ドル,ドル and complete the race. | 80ドル$ | 263ドル$ |
In the 2ドル$nd scenario, the starting and finishing position is the same as the 1ドル$st 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 2ドル$nd line.
In the 3ドル$rd scenario, the starting and finishing position is the same as the 1ドル$st and the 2ドル$nd 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 30 80 30 3 0 0 403 0 0 300 0 0 262
Yes No No
In the 1ドル$st 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 1ドル$st line.
| Order | Action | Time (sec.) | Total Time (sec.) |
|---|---|---|---|
| 1 | Start at position 0ドル$ and move to position 30ドル$. | 30ドル$ | 30ドル$ |
| 2 | Collect the 1ドル$st ball. | 1ドル$ | 31ドル$ |
| 3 | Move from position 30ドル$ to position 80ドル$. | 100ドル$ | 131ドル$ |
| 4 | Collect the 2ドル$nd ball. | 1ドル$ | 132ドル$ |
| 5 | Move from position 80ドル$ to position 30ドル$. | 150ドル$ | 282ドル$ |
| 6 | Collect the 3ドル$rd ball. | 1ドル$ | 283ドル$ |
| 7 | Move from position 30ドル$ to position 0ドル,ドル and complete the race. | 120ドル$ | 403ドル$ |
In the 2ドル$nd and the 3ドル$rd scenarios, the starting and finishing position is the same as the 1ドル$st 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 2ドル$nd and the 3ドル$rd line.
This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 5, 6, 7.
6 100 0 50 100 0 50 100 4 20 70 600 70 20 600 10 40 600 40 10 600
No Yes No Yes
This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6, 7.