시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 463 59 43 59.722%

문제

재혁이는 신기한 취미를 가지고 있다. 그 취미는 어떤 시간 T에 위치가 L 이상 R 이하인 모든 물병의 물을 맛보는 것이다!! 하지만, 가만히 앉아서 제자리에서 물만 먹던 재혁이는 비만에 걸릴 것을 우려하여 움직이기로 했다. 그리고 물병들은 자유분방하기 때문에 어떤 특정 상황이 되면 움직인다.

물병에는 1, 2, ..., N의 번호가 붙어 있고, i의 번호가 붙은 물병의 초기 위치는 -i이다. 재혁이의 초기 위치는 0이다. 재혁이와 물병들은 매초 순간이동을 하는데, 그 규칙은 다음과 같다.

  1. 재혁이는 1초마다 오른쪽으로 1씩 움직인다.
  2. 물병은 물이 쏟아질 것을 우려해서 함부로 움직이지 않는다. 재혁이가 이동한 후, 물병 1은 재혁이와의 거리가 D1+1 이상 차이나면 (재혁이의 위치)-1로 이동한다.
  3. 물병 1의 위치가 결정된 후, 물병 2는 물병 1과의 거리가 D2+1 이상 차이나면 (물병 1의 위치)-1로 이동한다. 같은 방식으로 물병 3, 4, ..., N이 순서대로 이동한다. 즉 물병 i는 물병 i-1과의 거리가 Di+1 이상 차이나면 (물병 i-1의 위치)-1로 이동한다.

재혁이는 무지막지하게 물을 먹다가 갑자기 어떤 시간 T와 구간 L, R에 대해서 자신이 몇개의 물을 마실 수 있는지 궁금해졌다. 그런데 물을 너무 많이 먹은 나머지 재혁이 자신도 물병이라고 착각하기 시작했다. 즉 재혁이의 위치가 L 이상 R 이하라면 질의의 답에 1을 더해야 한다. 재혁이를 위해 시간 T와 L, R들이 주어졌을 때 몇 개의 물병을 잡을 수 있는지 알려주자!

입력

첫 번째 줄엔 물병의 개수 N(1 ≤ N ≤ 500,000)과 질의의 개수 Q(1 ≤ Q ≤ 500,000)가 주어진다.

다음 N개의 줄에 Di(1 ≤ Di ≤ 1,000,000,000)가 주어진다.

다음 Q개의 줄에 Ti, Li, Ri(1 ≤ Ti, Li ≤ 1,000,000,000, Li ≤ Ri ≤ 1,000,000,000)가 주어진다.

출력

Q줄에 걸쳐 질의의 답을 출력한다. 즉 i번째 줄에는 시간 Ti에 위치가 Li 이상 Ri 이하인 물병이 몇 개인지 출력한다.

서브태스크 1 (10점)

  • Di = 1

서브태스크 2 (10점)

  • 1 ≤ N,Q,Ti, Li, Ri ≤ 1,000

서브태스크 3 (80점)

  • 위에서 주어진 제약조건 외 다른 조건 없음

예제 입력 1

3 6
2
5
3
1 2 4
2 2 4
3 2 4
4 2 4
5 2 4
6 2 4

예제 출력 1

0
1
1
2
1
2

시간 0 : 재혁이도 0의 위치이고, 각 물의 위치는 -1,-2,-3입니다. 거리가 3,6,4보다 작으므로 아무 물도 움직이지 않습니다.

시간 1 : 재혁이가 1의 위치입니다. 각 물의 위치는 -1,-2,-3인데, 재혁이와 첫 번째 물의 위치 차이는 2입니다. 따라서, 첫 번째 물이 이동하지 않습니다.

두번째와 세번째도 동일합니다.

시간 2 : 재혁이가 2의 위치입니다. 각 물의 위치는 -1,-2,-3인데, 재혁이와 첫 번째 물의 위치 차이가 3입니다. 거리가 3이므로 첫 번째 물이 1의 위치로 이동합니다. 그럼 물의 위치는 1,-2,-3이 됩니다. 여기서, 첫번째 물과 두번째 물의 위치 차이는 3이므로 6보다 작습니다. 따라서, 두번째 물은 이동하지 않습니다.

시간 3 : 재혁이가 3의 위치입니다. 첫 번째 물과 재혁이의 거리 차이가 2 이므로 이동하지 않습니다. 

시간 4 : 재혁이가 4의 위치입니다. 첫 번째 물과 재혁이의 거리 차이가 3이므로 이동합니다. 따라서, 첫번째 물은 3의 위치로 이동하고, 두번째 물과 첫번째 물의 거리 차이는 5이므로 이동하지 않습니다. 따라서, 물의 위치는 3,-2,-3이 되고 재혁이의 위치는 4입니다. 

시간 5 : 재혁이가 5의 위치입니다. 첫 번째 물과 재혁이의 거리 차이가 2이므로 이동하지 않습니다.

시간 6 : 재혁이가 6의 위치입니다. 첫 번째 물과 재혁이의 거리 차이가 3이므로 이동합니다. 따라서, 첫 번째 물은 5의 위치로 이동하고, 두 번째 물과 첫 번째 물의 거리 차이는 7이므로 이동합니다. 따라서 두 번째 물은 4의 위치로 이동합니다. 두 번째 물과 세 번째 물의 거리 차이는 7이므로 세 번째 물도 이동합니다. 따라서, 세 번째 물은 3으로 이동합니다.

시간 6일 때 각 물의 위치는 5,4,3 입니다.

예제 입력 2

4 2
1
1
1
1
2 1 4
1 3 6

예제 출력 2

2
0

출처

High School > 부산일과학고 > BSIS배 Code Festival G번

채점

  • 예제는 채점하지 않는다.