만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

마라톤 경주 2

시간 제한1.5초메모리 제한1024 MB

요약
길이 L인 도로에 놓인 N개의 공을 S에서 출발해 모두 모으고 G에서 끝내는 데 T초 안에 가능한지 각 질의마다 판단합니다.
난이도

어려움10점 중 9점

유형
그리디, 누적 합, 정렬
정답자
아직 제출이 없습니다

문제

JOI 거리는 동서 방향으로 놓인 길이 LL인 도로이다. 도로에서 서쪽 끝으로부터 ll미터(0≤l≤L0 \le l \le L) 떨어진 지점을 위치 ll이라고 한다.

올해 JOI 거리에서 처음으로 마라톤 경주가 열린다. 이 경주는 일반적인 경주와 다른 규칙을 따른다.

  • 경주 전에 도로 위에 공 NN개가 놓여 있다. ii번째 공은 위치 XiX_i에 있다. 같은 위치에 공이 여러 개 있을 수 있다.
  • 참가자는 지정된 위치에서 출발한다.
  • 참가자는 공 NN개를 모두 모은 뒤 지정된 위치에서 끝낸다. 제한 시간 안에 이를 마치면 경주를 완주한다. 단, 한 번 모은 공은 도로에 다시 놓으면 안 된다. 그렇게 하면 실격된다.

출발 위치, 도착 위치, 제한 시간은 아직 발표되지 않았다. 이들은 QQ개의 시나리오 중에서 정해진다. jj번째 시나리오에서 참가자는 위치 SjS_j에서 출발해 위치 GjG_j에서 끝내며, 제한 시간은 TjT_j초이다.

리에는 이 경주에 참가한다. 리에는 공 1개를 모으는 데 1초를 쓴다. 리가 공을 xx개 들고 있을 때 1미터를 이동하는 데는 x+1x+1초가 걸린다.

각 시나리오마다 리가 경주를 완주할 수 있는지 판별하는 프로그램을 작성하라.

입력

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

출력

QQ개의 줄을 출력한다. jj번째 줄에는 시나리오 jj에서 리가 경주를 완주할 수 있으면 Yes, 없으면 No를 출력한다.

제한

  • 1≤N≤500 0001 \le N \le 500\,000.
  • 1≤L≤500 0001 \le L \le 500\,000.
  • 0≤Xi≤L0 \le X_i \le L (1≤i≤N1 \le i \le N).
  • 1≤Q≤500 0001 \le Q \le 500\,000.
  • 0≤Sj≤L0 \le S_j \le L (1≤j≤Q1 \le j \le Q).
  • 0≤Gj≤L0 \le G_j \le L (1≤j≤Q1 \le j \le Q).
  • 1≤Tj≤500 0001 \le T_j \le 500\,000 (1≤j≤Q1 \le j \le Q).
  • 주어지는 값은 모두 정수이다.

예제3

  1. 예제 1

    입력
    3 100
30 80 30
3
0 100 403
0 100 300
0 100 262
    예상 출력
    Yes
Yes
No

  2. 예제 2

    입력
    3 100
30 80 30
3
0 0 403
0 0 300
0 0 262
    예상 출력
    Yes
No
No

  3. 예제 3

    입력
    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