슬라이드 개수

수업 과제로 슬라이딩 윈도우 알고리즘을 이용해 정수 배열을 분석한다. 정수 $N$개 $w_1, \ldots, w_N$과 상수 $C$가 주어지면, 알고리즘은 시작 인덱스 $s$와 끝 인덱스 $e$를 다음과 같이 관리한다.

• 처음에 $s = e = 1$로 둔다.
• $s \leq N$인 동안 다음을 반복한다.
  • $e+1 > N$이면 $s$를 1 증가시킨다.
  • 그렇지 않고 $w_s + \cdots + w_{e+1} > C$이면 $s$를 1 증가시킨다.
  • 그 밖의 경우에는 $e$를 1 증가시킨다.

실행 중에 나타나는 서로 다른 인덱스 쌍 $(s,e)$마다 윈도우 하나가 정해진다. $s \leq i \leq e$이면 원소 $w_i$는 윈도우 $(s,e)$에 속한다. $s > e$이면 윈도우는 비어 있다.

앞의 입력에서 나타나는 윈도우는 $(1,1)$, $(1,2)$, $(1,3)$, $(2,3)$, $(3,3)$, $(3,4)$, $(4,4)$, $(5,4)$, $(5,5)$, $(6,5)$이다. 각 원소 $w_i$에 대해, 실행 중 $w_i$가 속하는 서로 다른 윈도우의 개수를 구한다.

첫 줄에 원소의 개수 $N$($1 \leq N \leq 100\,000$)과 윈도우 상수 $C$($1 \leq C \leq 1\,000\,000$)이 주어진다.

둘째 줄에는 정수 $w_1, \ldots, w_N$($0 \leq w_i \leq C$)이 주어진다.

각 원소에 대해 입력 순서대로, 알고리즘 실행 중 그 원소가 속하는 서로 다른 윈도우의 개수를 출력한다.