Skills101
← All coding problems

Count Subarrays With Sum in a Range

hardArrays & Prefix Sums+40 XPTime limit 2s

Count the non-empty contiguous subarrays whose sum lies between lo and hi (both inclusive). The numbers can be negative.

Input:

  • line 1: n lo hi
  • line 2: n integers

Output: the number of such subarrays (use 64-bit integers).

Constraints: 1 ≤ n ≤ 10⁵, −10⁴ ≤ a[i] ≤ 10⁴, −10⁹ ≤ lo ≤ hi ≤ 10⁹.

Think about it: with prefix sums P, you need the number of pairs i < j with lo ≤ P[j] − P[i] ≤ hi. Checking all pairs is O(n²). Use merge sort on P: before merging two sorted halves, for each left value move two pointers through the right half to count the values in [left + lo, left + hi]. (A Fenwick tree over compressed prefix sums also works.)

Sample input 1

3 -2 2
-2 5 -1

Sample output 1

3

Sample input 2

4 0 0
0 0 0 0

Sample output 2

10

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.