Logo HelloWorld信息学奥赛题库

少儿编程

时间限制:1 s 空间限制:512 MB

#1801. [USACO14DEC]牛慢跑Cow Jog_Sliver

Statistics

题目描述

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

输入格式:

第一行包含两个整数N和T。
接下来N行,每行两个整数,表示N头牛的初始位置和速度。位置为非负整数,速度为正整数。这两个数都小于1000000000。

输出格式:

输出一个整数,表示T时间后,奶牛们有多少个小组。

输入样例#1:

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

输出样例#1:

3