24759번 - Slide Count 다국어

문제

In your programming class, you are given an assignment to analyze an integer array using a sliding window algorithm. Specifically, given $N$ integers $w_1, \ldots, w_N$ and some constant $C,ドル the sliding window algorithm maintains start and end indices $s$ and $e$ such that

• initially $s = e = 1$;
• as long as $s \leq N$:
  • if $e+1 > N,ドル then increment $s$;
  • else if $w_s + \cdots + w_{e+1} > C,ドル then increment $s$;
  • else increment $e$.

During the execution of this algorithm, each distinct pair of indices $(s,e)$ defines a window. An element $w_i$ belongs to the window defined by $(s,e)$ if $s \leq i \leq e$. Notice that if $s > e,ドル the window is empty.

Consider the first sample input below. The windows appearing during the execution of the algorithm are defined by $(1,1),ドル $(1,2),ドル $(1,3),ドル $(2,3),ドル $(3,3),ドル $(3,4),ドル $(4,4),ドル $(5,4),ドル $(5,5),ドル and $(6,5)$.

For each element $w_i,ドル determine how many different windows it belongs to during the execution of the sliding window algorithm.

입력

The first line of input contains two integers $N$ (1ドル \leq N \leq 100,000円$), which is the number of elements, and $C$ (1ドル \leq C \leq 1,000円,000円$), which is the sliding window constant.

The next line contains $N$ integers $w_1, \ldots, w_N$ (0ドル \leq w_i \leq C$).

출력

For each element, in order, display the number of different windows it belongs to during the execution of the algorithm.

제한

힌트