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;
}