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.
입력형식
* 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}.
