All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Cersei's Army



Queen of the Andals and the First Men, Protector of the Seven Kingdoms , Cersei Lannister is preparing her army for the upcoming Great War. Cersei’s city consists of ‘N’ citizens, she orders all of them to come and makes them stand in a line. Now, each citizen has some strength denoted by Ai, Ai can be positive, negative or zero (negative and zero for the old ones and children).

Little Finger has already found out about the average strength of the enemy’s army M, through his infamous spy birds.

Cersei calls a sequence of citizens A[L..R] Eligible for war, if the average of their strengths Ai, L<=i<=R is greater than or equal to M. Cersei is quite busy in preparing the strategy to tackle the mighty dragons, so she asks for your help in this difficult time.

           Average of A[L..R] = (Sum of Ai's for all L<=i<=R) / (R-L+1)

You need to find the number of sequences of citizens which are Eligible for war.

Input :

First line consists of an integer T, no. of test cases.

For each test case, there will be two lines;

first line contains two spaces separated integers N, M i.e. the number of citizens, and average strength of the enemy’s army respectively.

The next line contains N, space separated integers Ai, where i’th integer denotes strength of i’th citizen.

Output :

For each test case, a single new line consisting of an integer which denotes the number of sequences of citizens (A[L..R]) which are Eligible for war.

Constraints :

  • 1<=T<=5
  • 1<=N<=250000
  • -10^9<= Ai <=10^9
  • -10^9<= M <=10^9
4 1
1 2 0 -1

The strength of the citizens are A[4] = {1,2,0,-1} and M = 1. Here, 5 sequences have their average greater than or equal to 1. The sequences are as follows:

  • A[1,1] : average = 1 (1/1)
  • A[1,2] : average = 1.5 (3/2)
  • A[1,3] : average = 1 (3/3)
  • A[2,2] : average = 2 (2/1)
  • A[2,3] : average = 1 (2/2)
Time Limit: 1.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


Initializing Code Editor...
Your Rating:


This Problem was Asked in

ABV- Indian Institute of Information Technology and Management, Gwalior

Challenge Name

CodeMaze v3.0

View All Notifications