MCONVOI - Con Voi

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 rall(c) (c).rbegin(), (c).rend()
#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 1000000010
#define MOD 1000000007
#define N

vii P; //point
vi last, cnt; //cnt[i] = so cach nhay do dai i
vvii L;
int n;

void update( int i, int y, int add ) {
	cnt[i] = (cnt[i] + add) % MOD;
	L[i].pb(ii(y, (L[i].back().se + add) % MOD));
	last[i] = y;
}

void enter() {
	scanf("%d",&n);
	rep(i,n) {
		int x, y;
		scanf("%d%d",&x,&y);
		P.pb(ii(x,y));
	}
}

bool cmp(const ii &a, const ii &b) {
	return a.fi < b.fi || a.fi == b.fi && a.se > b.se;
}

void solve() {
	sort(all(P),cmp);
	L.resize(n+1); last.resize(n+1); cnt.resize(n+1);
	fill(all(last), INF); tr(L, it) it->pb(ii(INF, 0));
	update(0, -INF, 1);
	int best = 0;
	tr(P, it) {
		int A = lower_bound(all(last), it->se) - last.begin() - 1;
		/*typeof(L[0].rend()) B = lower_bound(rall(L[A]), ii(it->se, -INF));
		update(A+1, it->se, (cnt[A] - B->se) % MOD);*/
		update(A+1, it->se, (cnt[A] - lower_bound(rall(L[A]), ii(it->se, -INF))->se) % MOD);
		best = max(best, A+1);
	}
	printf("%d\n%d\n", best, (L[best].back().se + MOD) % MOD);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen( "input.txt", "r", stdin );
	//freopen( "output.txt", "w", stdout );
#endif
	enter();
	solve();
	return 0;
}

Download