Boring Day
Contest: Codeforces Round 955 (Div. 2, with prizes from NEAR!)
Difficulty rating: 1200
Tags: binary search, data structures, dp, greedy, two pointers

On another boring day, Egor got bored and decided to do something. But since he has no friends, he came up with a game to play.

Egor has a deck of $$$n$$$ cards, the $$$i$$$-th card from the top has a number $$$a_i$$$ written on it. Egor wants to play a certain number of rounds until the cards run out. In each round, he takes a non-zero number of cards from the top of the deck and finishes the round. If the sum of the numbers on the cards collected during the round is between $$$l$$$ and $$$r$$$, inclusive, the round is won; otherwise, it is lost.

Egor knows by heart the order of the cards. Help Egor determine the maximum number of rounds he can win in such a game. Note that Egor is not required to win rounds consecutively.

Input format:
Each test consists of several test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases. This is followed by a description of the test cases.

The first line of each test case contains three integers $$$n$$$, $$$l$$$, and $$$r$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le l \le r \le 10^9$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the numbers on the cards from top to bottom.

It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^{5}$$$.

Output format:
For each test case, output a single number — the maximum number of rounds Egor can win.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Egor can win $$$3$$$ rounds:

- In the first round, take the top $$$2$$$ cards with values $$$2$$$ and $$$1$$$ and win, as their sum is $$$3$$$. After this, the deck will look like this: $$$[11, 3, 7]$$$.
- In the second round, take the top card and lose, as its value $$$11$$$ is greater than $$$r = 10$$$. After this, the deck will look like this: $$$[3, 7]$$$.
- In the third round, take the top card with value $$$3$$$ and win. After this, the deck will look like this: $$$[7]$$$.
- After this, in the fourth round, Egor only has to take the last card in the deck with value $$$7$$$ and win again.

In the second test case, Egor cannot win any rounds, no matter how hard he tries.

In the third test case, you can take one card in each round, then the first and third rounds will be losing, and the second round will be winning.

In the fourth test case, you can take two cards in each round and always win.

Example input:
8
5 3 10
2 1 11 3 7
10 1 5
17 8 12 11 7 11 21 13 10 8
3 4 5
3 4 2
8 12 25
10 7 5 13 8 9 12 7
2 3 3
5 2
9 7 9
2 10 5 1 3 7 6 2 3
1 8 10
9
5 5 6
1 4 2 6 4

Example output:
3
0
1
4
0
3
1
2

Editorial:
Solution 1:
Let $$$dp[i]$$$ — the maximum number of rounds won by Egor for the first $$$i$$$ elements (top cards). It is possible to come up with a solution in $$$O(n^{2})$$$ right now. For each state of the dynamic programming $$$i$$$, you can either skip the next card (not take it in any winning segment), or iterate over the length of the segment that will start with the next card. If you calculate prefix sums and compute the sum over a segment in $$$O(1)$$$, the solution works exactly in $$$O(n^{2})$$$.
Let's try to optimize the transitions in such a dynamic.
First, it can be noticed that all $$$a_{i}$$$ are positive, which means that the sum of the segment $$$(a, b)$$$ will be less than $$$(a, b + 1)$$$. This means that the first suitable segment (with a sum $$$\ge l$$$) can be found using binary search or two pointers.
Secondly, if the segment has a suitable sum (from $$$l$$$ to $$$r$$$), it does not make sense to increase its length, as this can only worsen the answer.
Thus, for each state of the dynamic programming, there are only $$$O(1)$$$ transitions, so the entire problem can be solved in $$$O(n)$$$ or $$$O(n\log n)$$$.
Solution 2:
Let's try to solve the problem greedily. Let's look for a segment $$$(a, b)$$$ in the prefix such that the sum of all its elements is not less than $$$l$$$ and not greater than $$$r$$$, and among all such segments, we will take the segment with the minimum $$$b$$$. After that, we will consider that the array starts from the $$$(b + 1)$$$-th element and continue to search for the next segment in the same way.
How to find $$$(a, b)$$$? Let's start by finding the minimum prefix $$$k$$$ (which is also the segment $$$(1, k)$$$) such that the sum of the elements in it is $$$\ge l$$$. If this sum is also not greater than $$$r$$$, then this prefix is the segment we need $$$(a, b)$$$. Otherwise, we know that the sum of the elements in any subsegment of this prefix that does not contain the last element $$$a_{k}$$$ is less than $$$l$$$, so we can try to find a subsegment that ends at $$$k$$$, for this, we can iterate over the left boundary from $$$1$$$ to $$$k$$$. At the same time, the sum of the elements in the iterated segment will decrease and it may happen again that at some point it becomes $$$< l$$$, in this case, we already know that we will not find the required segment with the right boundary $$$k$$$, so it needs to be increased (again until the sum becomes $$$\ge l$$$). By repeating these actions, we will either find the required segment $$$(a, b)$$$, or the right boundary will become equal to $$$n$$$. The algorithm is nothing but "two pointers", we keep two boundaries $$$l$$$ and $$$r$$$ and move them only to the right, so in total, this all works in $$$O(n)$$$.