Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<stdio.h>
- #include<algorithm>
- #include<set>
- #include<map>
- #include<queue>
- #include<stack>
- #include<deque>
- #include<vector>
- #include<string>
- #include<math.h>
- using namespace std;
- #define INF 1000000001
- #define lint long long
- #define pb push_back
- #define mp make_pair
- #define MOD 1000000007
- lint t;
- lint a[100005];
- lint d[100005];
- int main()
- {
- freopen("cowjog.in","r",stdin);
- freopen("cowjog.out","w",stdout);
- int n,i;
- scanf("%d %lld",&n,&t);
- for(i=1;i<=n;++i)
- {
- lint x,v;
- scanf("%lld %lld",&x,&v);
- a[n+1-i]=x+v*t;
- }
- for(i=1;i<=n;++i)
- {
- d[i]=INF*1ll*INF+INF;
- }
- for(i=1;i<=n;++i)
- {
- int l=-1,r=n+1;
- while(r-l>1)
- {
- int mid=(r+l)/2;
- if(d[mid]<=a[i])
- {
- l=mid;
- }
- else r=mid;
- }
- d[l+1]=a[i];
- }
- for(i=n;i>0;--i)
- {
- if(d[i]<INF*1ll*INF+INF)
- {
- printf("%d\n",i);
- return 0;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement