31625번 - Marathon Race 2 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 145 | 39 | 34 | 26.772% |
문제
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_i$. 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 collect 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_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 ≤ N ≤ 500\, 000$.
- $1 ≤ L ≤ 500\, 000$.
- $0 ≤ X_i ≤ L$ ($1 ≤ i ≤ N$).
- $1 ≤ Q ≤ 500\, 000$.
- $0 ≤ S_j ≤ L$ ($1 ≤ j ≤ Q$).
- $0 ≤ G_j ≤ L$ ($1 ≤ j ≤ Q$).
- $1 ≤ T_j ≤ 500\, 000$ ($1 ≤ j ≤ Q$).
- Given values are all integers.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 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. |
예제 입력 1
3 100 30 80 30 3 0 100 403 0 100 300 0 100 262
예제 출력 1
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.
예제 입력 2
3 100 30 80 30 3 0 0 403 0 0 300 0 0 262
예제 출력 2
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.
예제 입력 3
6 100 0 50 100 0 50 100 4 20 70 600 70 20 600 10 40 600 40 10 600
예제 출력 3
No Yes No Yes
This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6, 7.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호