레이팅 미적용농부 존(Farmer John)은 키를 재기 위해 N마리 (1 <= N <= 100,000)의 소를 한 줄로 세웠다. 소 i의 키는 H_i (1 <= H_i <= 1,000,000,000) 나노미터이다. FJ는 정밀한 측정을 신봉한다! 존은 카운티 축제의 소 사진 대회에 제출하기 위해, 소들의 연속한 부분 수열을 사진으로 찍고 싶어 한다.
축제에는 제출되는 모든 사진에 대한 아주 이상한 규칙이 있다. 사진에 담긴 소 무리의 키의 중앙값이 특정 기준 X (1 <= X <= 1,000,000,000) 이상이어야만 제출할 수 있다.
이 문제에서 배열 A[0...K]의 중앙값은 A를 정렬한 뒤의 A[ceiling(K/2)]로 정의한다. 여기서 ceiling(K/2)는 K/2를 가장 가까운 정수로 올림한 값이다 (K/2가 처음부터 정수라면 K/2 그 자체). 예를 들어 {7, 3, 2, 6}의 중앙값은 6이고, {5, 4, 8}의 중앙값은 5이다.
FJ가 사진 대회에 제출할 수 있는, 소들의 서로 다른 연속 부분 수열의 개수를 세는 것을 도와주자.
첫째 줄: 공백으로 구분된 두 정수 N과 X.
둘째 줄부터 N+1번째 줄까지: i+1번째 줄에 정수 H_i가 주어진다.
중앙값이 X 이상인 FJ의 소들의 부분 수열의 개수. 이 값은 32비트 정수에 담기지 않을 수 있음에 유의하라.
median.in · 출력을 쓸 파일 median.out4 6
10
5
6
27Input 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 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}.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > November > Gold