Subarrays with Sum in a Band

Difficulty: 1700 5000 ms 128 MB

two-pointers

All values are positive. Count the contiguous subarrays whose sum lies in [LO, HI].

Input: the first line has N, LO and HI; the second line has N positive integers.

Output: the number of subarrays with LO ≤ sum ≤ HI.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ a_i ≤ 1000
• 1 ≤ LO ≤ HI ≤ 10⁹

Sample Tests

4 3 6
1 2 3 4

5

3 100 200
1 2 3

0

Read the Editorial