（寒假集训） Cow Jog（二分优化的最长上升子数列）

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 2e9
#define met(a,b) memset(a,b,sizeof a)
typedef long long ll;
using namespace std;
const int N = 1e5+5;
const int M = 4e5+5;
ll m,t,v;
int cnt=0,n;
ll a[N],d[N],j,len;
int  LIS(ll *arr, int n){
    ll *dp=new ll [n+5];
    int  where, idx = 1;
    dp[idx] = arr[0];
    for (int i = 1; i < n; ++i){
        if (arr[i]>=dp[idx]){
            idx++;
            dp[idx] = arr[i];
        }
        else{
            where = upper_bound(dp+1, dp + idx+1, arr[i]) - dp;//非下降
            dp[where] = min(dp[where], arr[i]);
        }
    }
    delete[] dp;
    return idx;
}
 
int main() {
    scanf("%d%lld",&n,&t);
    for (int i = 1; i <=n; ++i) {
        scanf("%lld%lld",&m,&v);
        a[i]=m+t*v;
    }
    for(int i=n;i>0;i--){
        d[cnt++]=a[i];
    }
    printf ("%d\n", LIS(d,n));
    return 0;
}