All Tracks Algorithms Searching Binary Search Problem

E. Count the Subarrays.
Tag(s):

Binary Search, Easy, Prefix-Sums, Sorting

Problem
Editorial
Analytics

You are given an array of \(N\)  numbers. Count the number of subarrays having the absolute value of sum strictly greater than \(K\)   i.e \(|sum| > K\) .

 

Input Format

  • The first line contains a positive integer \(T\) , the number of test cases. 
  • Each test case contains a single integer \(N\)  which denotes the number of elements in the array.
  • The next line contains  \(N\)  space separated integers \(A_1, A_2, A_3, .... ,A_N\) denoting the elements in the array.

Output Format 

For each test case print the answer in a new line.

Constraints

  • \(1 <= T <= 10^3\)
  • \(1 <= N <=2*10^5\)
  • \(1<= K <= 10^{18}\)
  • \(|A_i| <=10^9\)
  • The sum of \(N\) over all test cases does not exceed \(2*10^5\)

 

SAMPLE INPUT
2
3 2
2 -2 3
5 0
2 -3 0 3 2
SAMPLE OUTPUT
2
13
Explanation

1. In the first Test Case, the subarrays with sum greater than 2 are

{3}  Sum=3

{2,-2,3} Sum= 2 -2 + 3 = 3

2. In the 2nd test Case, there are total 15 subarrays.

All except {0}  {-3,0,3} have sum greater than 0.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications

?