Subarrays With Product Less Than K
mediumArrays & Prefix Sums+20 XPTime limit 2s
All numbers in the array are positive. Count the contiguous subarrays whose product is strictly less than k.
Input:
- line 1:
n k - line 2:
npositive integers
Output: the number of such subarrays (use 64-bit integers).
Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ a[i] ≤ 1000, 1 ≤ k ≤ 10⁶.
Think about it: use a sliding window. Extend it to the right, multiplying the product; while the product is ≥ k, divide out the leftmost element. Every window [l..r] that survives contributes r − l + 1 subarrays ending at r. (With k ≤ 1 the answer is 0 — no product of positive integers is below 1.)
Sample input 1
4 100 10 5 2 6
Sample output 1
8
Sample input 2
3 1 1 2 3
Sample output 2
0
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).