oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

median_usaco Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

median_usaco.txt

Problem 1: Above the Median [Brian Dean]

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.

PROBLEM NAME: median

INPUT FORMAT:

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

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

SAMPLE INPUT (file median.in):

4 6
10
5
6
2

INPUT DETAILS:

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

OUTPUT FORMAT:

* Line 1: The number of subsequences of FJ's cows that have median at
        least X. Note this may not fit into a 32-bit integer.

SAMPLE OUTPUT (file median.out):

7

OUTPUT DETAILS:

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}.

Tags

USACO 2011 November Gold, Data Structure, Fenwick

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100101s16MBAverage

Judge Compile Command

g++-8 ans.cpp -o median_usaco -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.