问题 1111. -- 公路(road.cpp)

1111: 公路(road.cpp)

时间限制: 1 Sec  内存限制: 128 MB
提交: 39  解决: 29
[提交][状态][讨论版]

题目描述

有一条单向的高速公路,只有一条车道,有n(1<=n<=100000)辆车在车高速路上行驶。他们的车速可能不同。但因为只有一条车道,所以不存在超车的可能。如果一辆车追上了前车,它就只能减速,与前车以同样的速度行驶,这样它们可以成为一个group。这些汽车的体积可以忽略不计。问经过T单位时间,高速公路上一共有多少个group。(当T时刻时,所有位置相同的汽车称为一个group)。

输入

第一行两个整数N,T(1<=T<=1000000000)。

接下来N行,每行包含两个整数,分别表示一辆车的初始位置和初始速度。

输出

一个整数,表示T时刻后有多少个group。

样例输入

5 3
0 1
1 2
2 3
3 2
6 1

样例输出

3

提示

来源

[提交][状态]