문제
JOI 애비뉴는 동서 방향으로 길이가 L인 도로입니다. 이 도로의 서쪽 끝에서 l 미터 떨어진 지점을 "위치 l"이라고 합니다.
올해 JOI 애비뉴에서 첫 번째 마라톤 경주가 열릴 예정입니다. 이 경주는 일반적인 경주와는 다른 규칙을 가지고 있으며, 다음과 같이 설명됩니다:
경주 전에 N개의 공이 도로에 배치됩니다. i번째 공(1 ≤ i ≤ N)은 위치 Xi에 배치됩니다. 여러 개의 공이 같은 위치에 배치될 수 있습니다.
참가자는 지정된 위치에서 출발합니다.
참가자는 N개의 공을 모두 모은 후 지정된 위치로 돌아옵니다. 이 작업을 지정된 시간 내에 완료하면 경주를 완주한 것으로 간주됩니다. 단, 참가자가 공을 한 번 모은 후에는 그 공을 도로에 놓을 수 없으며, 그렇지 않으면 경주에서 실격됩니다.
출발 및 도착 위치와 시간 제한은 아직 발표되지 않았지만, Q개의 시나리오에서 선택될 것이라는 정보가 있습니다. j번째 시나리오(1 ≤ j ≤ Q)에서는 참가자가 위치 Sj에서 출발해 위치 Gj에서 경주를 마치며, 시간 제한은 Tj 초입니다.
Rie는 이 마라톤 경주에 참가합니다. 그녀는 공을 1개 모으는 데 1초가 걸립니다. 공을 x개 들고 있을 때, 1미터 이동하는 데 x+1초가 걸립니다.
JOI 애비뉴의 정보, 공의 위치, 그리고 시나리오가 주어졌을 때, 각 시나리오에 대해 Rie가 경주를 완주할 방법이 존재하는지 여부를 판단하는 프로그램을 작성하세요.
입력
다음 데이터를 표준 입력에서 읽어들입니다.
N L
X1 X2 · · · XN
Q
S1 G1 T1
S2 G2 T2
.
.
.
SQ GQ TQ
[제약 조건]
1 ≤ N ≤ 500,000
1 ≤ L ≤ 500,000
0 ≤ Xi ≤ L (1 ≤ i ≤ N)
1 ≤ Q ≤ 500,000
0 ≤ Sj ≤ L (1 ≤ j ≤ Q)
0 ≤ Gj ≤ L (1 ≤ j ≤ Q)
1 ≤ Tj ≤ 500,000 (1 ≤ j ≤ Q)
주어진 값은 모두 정수입니다.
출력
표준 출력으로 Q개의 줄을 출력합니다. j번째 줄(1 ≤ j ≤ Q)에는 j번째 시나리오에서 Rie가 경주를 완주할 방법이 존재하면 "Yes"를, 그렇지 않으면 "No"를 출력하세요.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 7점 | N ≤ 7, Q ≤ 10, Sj = 0, Gj = 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점 | 추가 제약 조건 없음 |
예제1
3100
308030
3
0100403
0100300
0100262
Yes
Yes
No
첫 번째 시나리오에서 참가자는 위치 0에서 출발해 위치 100에서 경주를 마치며, 시간 제한은 403초입니다. Rie는 아래와 같은 방식으로 263초 안에 경주를 완주할 수 있으므로, 첫 번째 줄에 "Yes"를 출력합니다.
순서 행동 시간(초) 총 시간(초)
1. 위치 0에서 위치 30으로 이동 30 30
2. 첫 번째 공 수집 1 31
3. 세 번째 공 수집 1 32
4. 위치 30에서 위치 80으로 이동 150 182
5. 두 번째 공 수집 1 183
6. 위치 80에서 위치 100으로 이동 후 경주 완주 80 263두 번째 시나리오에서는 출발 및 도착 위치가 첫 번째 시나리오와 동일하지만 시간 제한이 300초입니다. Rie는 위와 동일한 방법으로 263초 안에 경주를 완주할 수 있으므로, 두 번째 줄에도 "Yes"를 출력합니다.
세 번째 시나리오에서는 출발 및 도착 위치가 첫 번째와 두 번째 시나리오와 동일하지만, 시간 제한이 262초입니다. 이 경우, Rie가 시간 내에 경주를 완주할 방법이 존재하지 않으므로, 세 번째 줄에는 "No"를 출력합니다.
이 입력 예시는 소과제 2, 3, 4, 5, 6, 7의 제약 조건을 만족합니다.
예제2
3100
308030
3
00403
00300
00262
Yes
No
No
첫 번째 시나리오에서 참가자는 위치 0에서 출발해 위치 0에서 경주를 마치며, 시간 제한은 403초입니다. Rie는 아래와 같은 방식으로 403초 안에 경주를 완주할 수 있으므로, 첫 번째 줄에 "Yes"를 출력합니다.
순서 행동 시간(초) 총 시간(초)
1. 위치 0에서 위치 30으로 이동 30 30
2. 첫 번째 공 수집 1 31
3. 위치 30에서 위치 80으로 이동 100 131
4. 두 번째 공 수집 1 132
5. 위치 80에서 위치 30으로 이동 150 282
6. 세 번째 공 수집 1 283
7. 위치 30에서 위치 0으로 이동 후 경주 완주 120 403두 번째와 세 번째 시나리오에서는 출발 및 도착 위치가 첫 번째 시나리오와 동일하지만, 시간 제한이 각각 300초와 262초입니다. 두 시나리오 모두에서 Rie가 시간 내에 경주를 완주할 방법이 존재하지 않으므로, 두 번째와 세 번째 줄에는 각각 "No"를 출력합니다.
이 입력 예시는 소과제 1, 2, 3, 4, 5, 6, 7의 제약 조건을 만족합니다.
예제3
6100
050100050100
4
2070600
7020600
1040600
4010600
No
Yes
No
Yes
이 입력 예시는 소과제 2, 3, 4, 5, 6, 7의 제약 조건을 만족합니다.