#4398. USACO 2014 December Contest, Bronze Cow Jog
USACO 2014 December Contest, Bronze Cow Jog
题目描述
奶牛们又出来锻炼蹄子了!有头奶牛在一条无限长的单车道跑道上慢跑(1 <= <= 100,000)。每头奶牛从跑道上的不同位置出发,有些奶牛的慢跑速度不同。
由于跑道只有一条车道,奶牛们不能相互超越。当一头速度较快的奶牛追上另一头奶牛时,她必须减速以避免撞到另一头奶牛,从而加入同一个跑步群体。
最终,不会再有奶牛相互碰撞。农夫约翰想知道当这种情况发生时,还会剩下多少个群体。请帮助他计算这个数量。
输入格式
- 第1行:输入包含整数。
- 接下来行:每行包含一头奶牛的初始位置和速度。位置是一个非负整数,速度是一个正整数;两个数都最多为10亿。所有奶牛都从不同的位置出发,并且在输入中会按位置递增的顺序给出。
输出格式
- 一行:一个整数,表示剩余的群体数量。
样例
样例输入
5
0 1
1 2
2 3
3 2
6 1
样例输出
2
数据范围
1 <= <= 100,000,位置为非负整数,速度为正整数,且均不超过10亿