P3111 [USACO14DEC] Cow Jog S

题目描述

有 $N$ 头奶牛在一个单人的超长跑道上慢跑,每头牛的起点位置都不同。由于是单人跑道,所有他们之间不能相互超越。当一头速度快的奶牛追上另外一头奶牛的时候,他必须降速成同等速度。我们把这些跑走同一个位置而且同等速度的牛看成一个小组。 请计算经过 $T$ 个单位时间后,奶牛们将分为多少小组。

输入格式

第一行输入包含两个整数 $N$ 和 $T$。 下面 $N$ 行,第 $i$ 行包含两个整数 $x_i$ 和 $v_i$,表示单头牛的初始位置和速度。

输出格式

输出一行一个数字表示答案。

说明/提示

$1\le T\le10^9$,$1\le N\le10^5$。 $1\le x_i,v_i\le10^9$,且保证所有牛的起始位置不同,这些位置将按递增顺序给出。