Advertisement
Guest User

Untitled

a guest
Dec 16th, 2014
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 KB | None | 0 0
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<algorithm>
  4. #include<set>
  5. #include<map>
  6. #include<queue>
  7. #include<stack>
  8. #include<deque>
  9. #include<vector>
  10. #include<string>
  11. #include<math.h>
  12. using namespace std;
  13.  
  14. #define INF 1000000001
  15. #define lint long long
  16. #define pb push_back
  17. #define mp make_pair
  18. #define MOD 1000000007
  19.  
  20. lint t;
  21. lint a[100005];
  22. lint d[100005];
  23. int main()
  24. {
  25.     freopen("cowjog.in","r",stdin);
  26.     freopen("cowjog.out","w",stdout);
  27.     int n,i;
  28.     scanf("%d %lld",&n,&t);
  29.  
  30.     for(i=1;i<=n;++i)
  31.     {
  32.         lint x,v;
  33.         scanf("%lld %lld",&x,&v);
  34.         a[n+1-i]=x+v*t;
  35.     }
  36.  
  37.     for(i=1;i<=n;++i)
  38.     {
  39.         d[i]=INF*1ll*INF+INF;
  40.     }
  41.     for(i=1;i<=n;++i)
  42.     {
  43.         int l=-1,r=n+1;
  44.  
  45.         while(r-l>1)
  46.         {
  47.             int mid=(r+l)/2;
  48.             if(d[mid]<=a[i])
  49.             {
  50.                 l=mid;
  51.             }
  52.             else r=mid;
  53.         }
  54.         d[l+1]=a[i];
  55.     }
  56.     for(i=n;i>0;--i)
  57.     {
  58.         if(d[i]<INF*1ll*INF+INF)
  59.         {
  60.             printf("%d\n",i);
  61.             return 0;
  62.         }
  63.     }
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement