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...