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

출력 예

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 November Contest, Gold Division 1

USACO 2011, Gold Division, Gold

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

3734 : Above the Median - Gold Division

문제

입력형식

출력형식

입력 예

출력 예

출처