有N (1 <= N <= 100,000)头奶牛在一个单人的超长跑道上慢跑,每头牛的起点位置都不同。由于是单人跑道,所有他们之间不能相互超越。当一头速度快的奶牛追上另外一头奶牛的时候,他必须降速成同等速度。我们把这些跑走同一个位置而且同等速度的牛看成一个小组。
请计算T (1 <= T <= 1,000,000,000)时间后,奶牛们将分为多少小组。
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
#define ll long long
ll now[N];
ll T,n;
int main(){
cin>>n>>T;
for(ll i=1,x,v;i<=n;i++){
scanf("%lld%lld",&x,&v);
x-=1e9;
now[i]=x+v*T;
}
ll ans=1;
for(int i=n-1;i>=1;i--){
if(now[i]>=now[i+1])
now[i]=now[i+1];
else ans++;
}
cout<<ans<<endl;
}