레이팅 미적용설명
농부 존(Farmer John)의 N마리 (1 <= N <= 50,000) 소들이 1차원 울타리를 따라 풀을 뜯고 있다. 소 i는 위치 x(i)에 서 있고 키가 h(i)이다 (1 <= x(i),h(i) <= 1,000,000,000).
어떤 소는 왼쪽으로 거리 D 이내에 자기 키의 두 배 이상인 소가 있고, 오른쪽으로도 거리 D 이내에 자기 키의 두 배 이상인 소가 있으면 "붐빈다"고 느낀다 (1 <= D <= 1,000,000,000). 붐비는 소는 우유를 덜 생산하므로, 농부 존은 그런 소의 수를 세고 싶어 한다. 존을 도와주자.
제약
입력 형식
첫째 줄: 두 정수 N과 D.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 정수 x(i)와 h(i)가 주어진다. N마리의 소의 위치는 모두 서로 다르다.
출력 형식
붐비는 소의 수.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
crowded.in · 출력을 쓸 파일 crowded.out예제 1
입력
6 4
10 3
6 2
5 3
9 7
3 6
11 2출력
2설명
Output details: The cows at positions x=5 and x=6 are both crowded.
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > November > Silver
태그