Problems Base course RU

The dry spell

two pointers sliding window prefix sums science and physics geodata

A series of daily rainfall is given. For each limit S, find the longest period of consecutive days during which no more than S fell in total. There are several limits, and each needs its own answer.

The second and third tests are the daily rainfall of Almaty for 1941–2025 (the ERA5 reanalysis via Open-Meteo), in tenths of a millimetre: 31,046 days.

Input

The first line holds n and q (1 ≤ n ≤ 2·10⁵, 1 ≤ q ≤ 10). The second holds n integers from 0 to 10⁶, the third q limits S from 0 to 2·10¹¹.

Output

For each limit, the length of the longest period; 0 if even a single day exceeds the limit.

Examples

Example 1

Input

10 4
5 0 0 12 0 3 0 0 0 9
0 3 5 100

Output

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Rainfall is never negative. What does that mean for the window’s sum when its left edge moves right?

2The idea

The sum of non-negative numbers only decreases when the left edge moves and only increases when the right edge moves. So two pointers fit: the right one goes through the days, and the left one catches up whenever the sum exceeds the limit. For each right edge the left one ends up in the leftmost position at which the window still fits within the limit, so we see the longest window with that right edge.

3Walkthrough

Each pointer passes over the series once: O(n) per limit, O(n·q) for all. It can also be done differently: with prefix sums and binary search, look for the leftmost suitable start for each right edge, O(n log n) per limit. That solution also works when two pointers do not.

And when do they not work? If the series can contain negative numbers, moving the left edge may increase the sum, and “catching up” is not allowed. Then only prefix sums help.

Sums reach 2·10¹¹; in Go you need int64.

3+Solution

4Complexity

O(n) for one limit, O(n·q) for all.

5Common mistakes

Enumerating starts. Growing a window from each day while it fits is O(n·L), and with large limits the windows are long.
A limit smaller than one day. If even a single day exceeds the limit, the answer is 0, and the left pointer goes past the right one; check that your code survives this.
A 32-bit sum. In the sixth test the sum of all days is 2·10¹¹.

Algorithms behind it

TEC Technique Two pointers Two indices move only forwards and replace enumerating pairs or ranges with one pass in O(n). O(n) 2 problems TEC Technique Prefix sums The sum of any segment in O(1) after one pass; the two-dimensional version gives the sum of any rectangle of a picture. O(n) to build, O(1) per query 2 problems