시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.234 초 1024 MB20711810267.550%

문제

효원이는 해외 유명 Online Judge 사이트인 Codepowers의 회원이다. Codepowers는 회원들에게 레이팅 시스템을 제공하는데, 매주 열리는 라운드에 참여하면 레이팅을 매겨준다.

효원이는 라운드에 $N$번 참여했다. 효원이의 초기 레이팅 $X$와 각 라운드에 참여한 후 레이팅의 증감이 수열 $A$로 주어진다. 수열 $A$의 원소 $A_i$는 $i$번째 라운드에 참여한 직후의 레이팅에서 그 라운드에 참여하기 직전의 레이팅을 뺀 값이다.

자신이 기대한 만큼 높은 레이팅 점수를 받지 못한 효원이는 목표 레이팅보다 낮은 레이팅을 언제 받았는지 궁금해한다.

$M$개의 쿼리가 주어진다. 각 쿼리마다 효원이가 $l$번째 라운드에 참여한 직후부터 $r$번째 라운드에 참여하기 직전까지 레이팅이 $K$보다 낮은 횟수를 출력하라.

입력

첫째 줄에 정수 $N$, $M$, $K$, $X$가 주어진다. $(1 \leq N \leq 10^5, 1 \leq M \leq 10^6, -10^9 \leq K \leq 10^9, -10^4 \leq X \leq 10^4)$

둘째 줄에는 수열 $A$를 이루고 있는 정수 $A_i$가 주어진다. $(-10^4 \leq A_i \leq 10^4)$

셋째 줄부터 $M$줄에 걸쳐 쿼리가 주어진다. 각 줄에는 $j$번째 쿼리의 정보 $l_j$, $r_j$가 주어진다. $(1 \leq l_j < r_j \leq N+1)$

출력

$M$줄에 걸쳐 각 쿼리의 답을 출력한다.

예제 입력 1

10 6 1019 1000
7 -5 5 8 1 3 6 -7 7 10
3 6
1 5
4 5
5 9
3 8
9 11

예제 출력 1

3
4
1
2
3
0

예제 1을 그림으로 표현하면 다음과 같다.

출처

University > 홍익대학교 > 2022 홍익대학교 HI-ARC 프로그래밍 경진대회 D번