laekov

新题么。略水。

就一个序列，如果起点单增的话只要终点单增就不会冲突。

然后最少单增子序列覆盖=最长不降子序。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long dint;

#define _l (long long int)

const int maxn = 100009;

int n, m, a[maxn], t[maxn], s;

dint v[maxn], v0[maxn];

int btQry(int p) {

int s = 0;

for (; p; p -= (p & -p))

s = max(s, t[p]);

return s;

}

void btChg(int p, int v) {

for (; p <= n; p += (p & -p))

t[p] = max(t[p], v);

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

scanf("%d%d", &n, &m);

for (int i = 0; i < n; ++ i) {

int p, s;

scanf("%d%d", &p, &s);

v0[i] = p + _l s * m;

v[i] = v0[i];

}

sort(v, v + n);

memset(t, 0, sizeof(t));

for (int i = 0; i < n; ++ i) {

int a = n - (lower_bound(v, v + n, v0[i]) - v);

int f = btQry(a) + 1;

btChg(a, f);

}

printf("%d\n", btQry(n));

}