지하철 혼잡 보정 구간

문제

한 지하철 노선의 운영 시스템은 열차가 각 역을 지날 때 혼잡 예측값을 보정한다. 운행 방향으로 나열된 N개 역마다 보정값이 하나씩 기록되어 있으며, 각 값은 -1, 0, 1 중 하나다. -1은 예측값을 한 단계 내리는 보정, 1은 한 단계 올리는 보정, 0은 그대로 두는 보정이다. 이 값은 실제 승객 수가 아니므로 음수가 기록되어도 정상적인 자료다. 분석 담당자는 연속한 역들로 이루어진 구간을 골라 보정값의 합이 정확히 K가 되는 경우를 세려고 한다. 구간은 시작 역 L과 끝 역 R로 나타내며 1≤L≤R≤N을 만족해야 한다. 해당 구간의 합은 L번 역부터 R번 역까지 기록된 모든 보정값을 더한 값이다. 중간 역을 건너뛰거나 운행 방향의 끝에서 처음으로 이어지는 구간은 허용하지 않는다. 시작 역이나 끝 역이 다르면 서로 다른 구간으로 센다. 보정값의 나열이 같거나 합이 같더라도 양 끝 위치가 다르면 각각 답에 포함한다. 역 하나만 포함하는 구간도 허용하지만, 역을 하나도 포함하지 않는 빈 구간은 허용하지 않는다. 특히 K가 0일 때에도 빈 구간을 세어서는 안 된다. 보정값에는 음수와 0이 있으므로 역을 하나 더 포함했을 때 구간의 합이 커질 수도, 작아질 수도, 그대로일 수도 있다. 또한 전체 구간의 합이 K가 아니더라도 일부 구간의 합은 K일 수 있다. 분석은 구간의 길이를 제한하지 않으며, 조건을 만족하는 모든 구간의 개수를 요구한다. 입력으로 주어진 보정 기록과 목표값 K를 이용하여 이 개수를 구한다. 조건을 만족하는 구간이 없다면 답은 0이다. 같은 보정값이 길게 반복되면 구간의 수가 매우 많아질 수 있으므로, 출력할 정수를 저장할 수 있는 자료형을 사용해야 한다.

입력

첫 줄에 역의 수 N과 목표값 K가 주어진다. 1≤N≤100,000, -N≤K≤N이다.
둘째 줄에 운행 방향 순서의 보정값 A_1, A_2, …, A_N이 공백으로 주어진다. 각 A_i는 -1, 0, 1 중 하나다. 모든 수는 정수다.

출력

보정값의 합이 정확히 K인 비어 있지 않은 연속 구간의 개수를 한 줄에 정수로 출력한다. 조건을 만족하는 구간이 없으면 0을 출력한다.

5 0
1 -1 0 1 -1

7

4 2
1 0 1 -1

1

3 -1
0 1 0

0

출처: Devin.KR 자체 제작