Subarray Sum Ranges
UptoSkills Arena is organizing a coding contest! We need to find the number of subarrays whose sum falls within a given range [A, B]. A subarray is a contiguous part of an array.
Given an array of integers arr and two integers A and B, count how many subarrays arr[i..j] (inclusive) satisfy A <= sum(arr[i..j]) <= B.
Input
The first line contains an integer N, the size of the array. The second line contains two integers A and B. The third line contains N space-separated integers, the elements of the array arr.
Output
Print a single integer, the total count of subarrays whose sum is between A and B (inclusive).
Constraints
1 <= N <= 200000 -10^9 <= A, B <= 10^9 -10^9 <= arr[i] <= 10^9
Example 1
4 1 3 1 -1 2 1
8
Subarrays: [1] (sum 1), [-1, 2] (sum 1), [2] (sum 2), [1] (sum 1), [1, -1, 2] (sum 2), [-1, 2, 1] (sum 2), [2, 1] (sum 3). Total 7 subarrays.
Example 2
3 -2 2 1 -2 1
6
Subarrays: [1] (sum 1), [-2] (sum -2), [1] (sum 1), [1, -2] (sum -1), [-2, 1] (sum -1), [1, -2, 1] (sum 0). Total 6 subarrays.
Hints
Similar problems
- Minimum Cost Subarray with Sum at Least KHard
- Count Subarrays with Target SumEasy
- Longest Subarray With Sum XMedium
- Longest Subarray with Equal HalvesMedium
- Count Non-Negative SubarraysEasy
- Longest Subarray with Sum at Most KMedium
More topics: Sliding Window problems, Prefix Sums problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 1 3 1 -1 2 1
3 -2 2 1 -2 1