There are N cows jogging on an infinitely-long single-lane track (1 <= N <= 100,000). Each cow starts at a distinct position, and some cows jog at different speeds. With only one lane, cows cannot pass each other; when a faster cow catches up to another cow, she slows down and becomes part of the same group.

The cows will run for T minutes (1 <= T <= 1,000,000,000). Please help Farmer John determine how many groups will be left at this time. Two cows are part of the same group if they are at the same position at the end of T minutes.

Line 1: The two integers N and T.

Lines 2..1+N: Each contains the initial position and speed of a single cow (both nonnegative/positive integers at most 1 billion). All cows start at distinct positions, given in increasing order.

A single integer indicating how many groups remain after T minutes.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > December > Silver