P3111 [USACO14DEC] Cow Jog S

There are $N$ cows jogging on an infinitely long single-lane track, where $1 \le N \le 100000$. Each cow starts at a distinct position on the track, and some cows jog at different speeds. Since the track has only one lane, cows cannot pass each other. When a faster cow catches up to a slower cow, she must slow down to avoid running into her, becoming part of the same running group. The cows will run for $T$ minutes, where $1 \le T \le 1000000000$. Please determine how many groups remain at that time. Two cows are considered part of the same group if they are at the same position at the end of $T$ minutes.

- The first line contains two integers $N$ and $T$. - Each of the following $N$ lines contains two integers: the initial position and speed of a single cow. The position is a nonnegative integer and the speed is a positive integer; both are at most $10^9$. All cows start at distinct positions, given in increasing order.

Output a single integer indicating how many groups remain after $T$ minutes.

Translated by ChatGPT 5