A turnstile logs n entry events, each stamped with a time. Timestamps are given in non-decreasing order. For each event, report how many events (including this one) happened strictly within the last W time units - that is, how many logged events have a timestamp greater than (this event's timestamp) - W.
Because timestamps never decrease, this count is exactly the number of events whose timestamp t_j satisfies t_j > t_i - W, considering only events at or before the current one.
Line 1: two integers n and W.
Line 2: n space-separated integers, the timestamps in non-decreasing order.
One line with n space-separated integers: for each event (in order), the count of recent events as defined above.
Example 1
Input
5 3 1 2 3 4 5
Expected
1 2 3 3 3
Explanation
For the event at time 3, recent means timestamp > 0, so events at 1,2,3 count -> 3. For time 4, timestamp > 1 keeps 2,3,4 -> 3. For time 5, timestamp > 2 keeps 3,4,5 -> 3.
Example 2
Input
4 10 0 0 5 5
Expected
1 2 3 4
Explanation
W is large enough that every earlier event stays inside the window, so the counts simply grow: 1, 2, 3, 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →