Range Sums in a Window

Difficulty: 1400 5000 ms 128 MB

divide-and-conquer fenwick

Count the subarrays whose sum lies in [LO, HI].

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

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

Constraints:

• 1 ≤ N ≤ 10⁵
• |a_i| ≤ 10⁴
• |LO|, |HI| ≤ 10⁹

Sample Tests

4 3 6
2 1 3 4

5

1 0 0
5

0

Read the Editorial