MCONVOI - Con Voi

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <iostream>
using namespace std;

const int MOD = 1000000007;

struct Data {
	int m, s;	
};

int n;
pair<int,int> a[300030];
int py[300030], F[300030], S[300030];
Data it[300030 * 4];

inline Data merge(Data a, Data b) {
	if(a.m > b.m) return a;
	else if(a.m < b.m) return b;
	else {
		a.s = (a.s + b.s) % MOD;	
		return a;
	}
}

void update(int i, int l, int r, int p, int v, int s) {
	if(l==r) {
		if(it[i].m==v) it[i].s = (it[i].s+s) % MOD;
		else if(it[i].m<v) {
			it[i].m = v;
			it[i].s = s;	
		}
		return;		
	}
	int m = (l+r) / 2;
	if(p<=m) update(2*i,l,m,p,v,s);
	if(m<p) update(2*i+1,m+1,r,p,v,s);	
	it[i] = merge(it[2*i], it[2*i+1]);
}

Data get(int i, int l, int r, int ct) {
	if(r<=ct) return it[i];	
	int m = (l+r) / 2;
	if(m>=ct) return get(2*i,l,m,ct);
	else return merge(get(2*i,l,m,ct),get(2*i+1,m+1,r,ct));
}

int main() {
	scanf("%d", &n);
	for(int i=0;i<n;++i) {
		scanf("%d%d", &a[i].first, &a[i].second);	
		py[i] = a[i].second;
	}	
	sort(a, a+n);
	sort(py, py+n);
	for(int i=0;i<n;++i) a[i].second = lower_bound( py, py + n, a[i].second) - py;	
	for(int i=0;i<n;++i) if(i==0 || a[i].first!=a[i-1].first) {
		for(int j=i;j<n && a[j].first==a[i].first;++j) {
			Data d;
			if(a[j].second>0) d = get(1,0,n-1,a[j].second-1);
			else d.m = 0;
			F[j] = d.m + 1;
			if(F[j]==1) S[j] = 1;
			else S[j] = d.s;
		}
		for(int j=i;j<n && a[j].first==a[i].first;++j)
			update(1,0,n-1,a[j].second,F[j],S[j]);
	}
	int res = *max_element( F, F+n);
	int sum = 0;
	for(int i=0;i<n;++i) if(F[i]==res) sum = (sum + S[i]) % MOD;
	printf("%d\n%d\n", res, sum);
	return 0;
}

Download