PBCSEQ - Các đoạn nguyên
Tác giả: happyboy99x
Ngôn ngữ: C++
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)
#define INF 1000000000
#define N 100000
#define MAXVAL 1000000
vii a;
int n, dp[N+1], bit[MAXVAL+1];
bool cmp(const ii &a, const ii &b) {
return a.fi > b.fi || a.fi == b.fi && a.se < b.se;
}
void update( int i, int v ) {
for(; i <= MAXVAL; i += i & -i)
if( bit[i] == -1 || dp[bit[i]] < dp[v] ) bit[i] = v;
}
int sum( int i ) {
int ret = -1;
for(; i > 0; i -= i & -i)
if( bit[i] != -1 && (ret == -1 || dp[bit[i]] > dp[ret]) )
ret = bit[i];
return ret;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
scanf("%d",&n);
rep(i,n) {
int x, y; scanf("%d%d",&x,&y);
a.pb(ii(x,y));
}
sort(all(a),cmp); memset(bit, -1, sizeof bit);
rep(i,n) {
dp[i] = 1;
int x = sum(a[i].se);
if( x != -1 ) dp[i] = dp[x] + 1;
update(a[i].se, i);
}
printf("%d\n", *max_element(dp,dp+n));
return 0;
}