레이팅 미적용설명
소들이 또 발굽 운동을 하러 나왔다! 무한히 긴 1차선 트랙에서 N마리의 소(1 <= N <= 100,000)가 조깅을 하고 있다. 각 소는 트랙 위의 서로 다른 위치에서 출발하며, 소마다 조깅 속도가 다를 수 있다.
트랙이 1차선뿐이라 소들은 서로를 추월할 수 없다. 더 빠른 소가 다른 소를 따라잡으면, 부딪히지 않도록 속도를 줄여야 하고, 그 소와 같은 달리기 그룹의 일원이 된다.
결국에는 더 이상 소들이 서로 따라잡는 일이 없어진다. 농부 존은 그때 그룹이 몇 개 남을지 궁금하다. 이 수를 계산하는 것을 도와라.
제약
입력 형식
첫째 줄: 정수 N이 주어진다.
둘째 줄부터 1+N째 줄까지: 각 줄에 소 한 마리의 초기 위치와 속도가 주어진다. 위치는 음이 아닌 정수이고 속도는 양의 정수이며, 둘 다 최대 10억이다. 모든 소는 서로 다른 위치에서 출발하며, 위치가 증가하는 순서로 주어진다.
출력 형식
남는 그룹의 수를 정수 하나로 출력한다.
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:
입력을 읽을 파일
cowjog.in · 출력을 쓸 파일 cowjog.out예제 1
입력
5
0 1
1 2
2 3
3 2
6 1출력
2문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > December > Bronze
태그