Problem D
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.
Input
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$).
Output
For each element, in order, display the number of different windows it belongs to during the execution of the algorithm.
Sample Input 1 | Sample Output 1 |
---|---|
5 3 1 1 1 2 2 |
3 3 4 2 1 |
Sample Input 2 | Sample Output 2 |
---|---|
5 10 1 2 3 4 5 |
4 4 4 5 2 |