Perfect Subarrays

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given an array A, which consists of N integers. Also, you have an integer K.
Let's call a subarray A[L..R] perfect, if the average of the numbers A_{L}, A_{L + 1}, ..., A_{R  1}, A_{R} is greater than or equal to K.
I.e. the average of the numbers {2, 5, 9, 3} equals to 3.25.
So, your task is quite simple: you are to count the number of perfect subarrays of A.
Input
The first line contains two integers N and K.
The second line contains N integers, i'th integer denotes A_{i}. The array A is 1indexed.
Output
The first line should contain an integer, denoting the number of perfect subarrays of A.
Example
Input: 4 2 1 2 3 1 Output: 4
Explanation
In the test case N equals to 4, K equals to 2, A equals to {1, 2, 3, 1}. The following subarrays are perfect: [2..2], [3..3], [2..3], [1..3].
Scoring
10^{9} ≤ K ≤ 10^{9} for each test case;
10^{9} ≤ A_{i} ≤ 10^{9} for each test case;
Subtask 1 (10 points): 1 ≤ N ≤ 100;
Subtask 2 (39 points): 1 ≤ N ≤ 6000;
Subtask 3 (11 points): 1 ≤ N ≤ 150 000, K = 0;
Subtask 4 (20 points): 1 ≤ N ≤ 150 000;
Subtask 5 (20 points): 1 ≤ N ≤ 1 000 000;
Author:  kostya_by 
Editorial  http://discuss.codechef.com/problems/SUBARR 
Tags  bit, easy, fenwick, kostya_by, ltime07, prefixsum, segmenttree 
Date Added:  27112013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 