document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include <bits/stdc++.h>
  2. #define SZ(X) ((int)(X).size())
  3. #define ALL(X) (X).begin(), (X).end()
  4. #define REP(I, N) for (int I = 0; I < (N); ++I)
  5. #define REPP(I, A, B) for (int I = (A); I < (B); ++I)
  6. #define RI(X) scanf("%d", &(X))
  7. #define RII(X, Y) scanf("%d%d", &(X), &(Y))
  8. #define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
  9. #define DRI(X) int (X); scanf("%d", &X)
  10. #define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
  11. #define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
  12. #define RS(X) scanf("%s", (X))
  13. #define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
  14. #define MP make_pair
  15. #define PB push_back
  16. #define MS0(X) memset((X), 0, sizeof((X)))
  17. #define MS1(X) memset((X), -1, sizeof((X)))
  18. #define LEN(X) strlen(X)
  19. #define PII pair<int,int>
  20. #define VI vector<int>
  21. #define VPII vector<pair<int,int> >
  22. #define PLL pair<long long,long long>
  23. #define VPLL vector<pair<long long,long long> >
  24. #define F first
  25. #define S second
  26. typedef long long LL;
  27. using namespace std;
  28. const int MOD = 1e9+7;
  29. const int SIZE = 1e6+1;
  30. VPLL pp;
  31. int BIT[SIZE];
  32. void ins(int x,int v){
  33.     for(;x<SIZE;x+=x&-x)BIT[x]=max(BIT[x],v);
  34. }
  35. int qq(int x){
  36.     int res=0;
  37.     for(;x;x-=x&-x)res=max(BIT[x],res);
  38.     return res;
  39. }
  40. int LIS(LL a[],int N){
  41.     static LL d[SIZE];
  42.     REP(i,N)
  43.         d[i]=a[i];
  44.     sort(d,d+N);
  45.     int m=unique(d,d+N)-d;
  46.     REP(i,N){
  47.         a[i]=lower_bound(d,d+m,a[i])-d+1;
  48.     }
  49.     int an=0;
  50.     REP(i,N){
  51.         int me=qq(a[i])+1;
  52.         an=max(an,me);
  53.         ins(a[i],me);
  54.     }
  55.     return an;
  56. }
  57. LL a[SIZE];
  58. int main(){
  59.     DRII(n,D);
  60.     REP(i,n){
  61.         DRII(x,t);
  62.         pp.PB(MP(x+D*(LL)t,-x+D*(LL)t));
  63.         if(pp.back().F<0||pp.back().S<0)pp.pop_back();
  64.     }
  65.     sort(ALL(pp));
  66.     REP(i,SZ(pp))a[i]=pp[i].S;
  67.     printf("%d\\n",LIS(a,SZ(pp)));
  68.     return 0;
  69. }
');