USACO 2011 November Contest, Gold Division 1- Above the Median - Gold Division > 문제은행 : 정보올림피아드&알고리즘




3734 : Above the Median - Gold Division

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
1 회   
시도횟수
1 회   

문제

Farmer John has lined up his N (1 <= N <= 100,000) cows in a row to measure their heights; cow i has height H_i (1 <= H_i <= 1,000,000,000) nanometers--FJ believes in precise measurements! He wants to take a picture of some contiguous subsequence of the cows to submit to a bovine photography contest at the county fair.


The fair has a very strange rule about all submitted photos: a photograph is only valid to submit if it depicts a group of cows whose median height is at least a certain threshold X (1 <= X <= 1,000,000,000).

For purposes of this problem, we define the median of an array A[0...K] to be A[ceiling(K/2)] after A is sorted, where ceiling(K/2) gives K/2 rounded
up to the nearest integer (or K/2 itself, it K/2 is an integer to begin with). For example the median of {7, 3, 2, 6} is 6, and the median of {5, 4, 8} is 5.
Please help FJ count the number of different contiguous subsequences of his cows that he could potentially submit to the photography contest.
 ​

 


입력형식

* Line 1: Two space-separated integers: N and X.

* Lines 2..N+1: Line i+1 contains the single integer H_i.​ ​ 


출력형식

* Line 1: The number of subsequences of FJ's cows that have median at​ 


입력 예

4 6 10 5 6 2

출력 예

7

Hint!

FJ's four cows have heights 10, 5, 6, 2. We want to know how many contiguous subsequences have median at least 6.​

 

There are 10 possible contiguous subsequences to consider. Of these, only 7 have median at least 6. They are {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.​




USACO 2011, Gold Division, Gold

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP