fractal161's Qualifier
Player:
Event:
Tournament:
Status:
Approved
Score 1:
2,795,620
Score 2:
1,249,800
Total score:
2,022,710
Details:
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.