Submission #1368903

#TimeUsernameProblemLanguageResultExecution timeMemory
1368903ByeWorldBoat (APIO16_boat)C++20
9 / 100
300 ms22236 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast")
#define int long long
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 2010;
const int MAXA = 2e5+10;
const int SQRT = 450;
const ll INF = 2e12;
const int MOD = 1e9+7;
const int LOG = 30;
int sum(int a, int b){ 
	int te = a+MOD+b; 
	for(; te >= MOD; ) te -= MOD;
	return te;
}
void chsum(int &a, int b){ a = sum(a,b); }
int mul(int a, int b){ 
	a%=MOD; b%=MOD; return a*b%MOD; 
}
void chmul(int &a, int b){ a = mul(a,b); }
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }

int expo(int a, int b){
	if(b==0) return 1;
	int te = expo(a, b/2); te = mul(te,te); // temporary -> te
	return (b%2 ? mul(te, a) : te);
}

int n, k, l[MAXN], r[MAXN], val[MAXN][MAXN], dp[MAXN][MAXN], pr[MAXN][MAXN];
int inv[MAXN], way[MAXN][MAXN];
vector<pii> seg;

signed main(){ 
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;

	vector<int> cc; cc.pb(-1);
	for(int i=1; i<=n; i++){
		cin>>l[i]>>r[i];
		cc.pb(l[i]); cc.pb(r[i]+1);
	}
	sort(cc.begin(), cc.end());
	cc.resize(unique(cc.begin(), cc.end())-cc.begin());

	seg.pb({-1, -1});
	for(int i=1; i+1<cc.size(); i++) seg.pb({cc[i], cc[i+1]-1});
	
	k = seg.size()-1;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=k; j++){
			if(l[i]<=seg[j].fi && seg[j].se<=r[i]) val[i][j] = 1;
		}
	}

	inv[0] = 1; int run = 1;
	for(int i=1; i<=n; i++){
		chmul(run, i);
		inv[i] = expo(run, MOD-2);
	}

	for(int j=1; j<=k; j++){
		for(int i=1; i<=n; i++){
			int te = 1, siz = seg[j].se-seg[j].fi+1;
			
			if(siz < i){ way[j][i] = 0; continue; }
			
			for(int p=siz; p>=siz-i+1; p--) chmul(te, p);
			chmul(te, inv[i]);
			way[j][i] = te;
			// cout << j << ' '<< i << ' '<<way[j][i] <<" ywa\n";
		}
	}
	
	// for(auto [x,y] : seg) cout << x <<  ' ' << y << " y\n";
	for(int i=1; i<=n; i++){
		for(int j=1; j<=k; j++){
			// dp[i][j]
			int te = 0;
			bool can = 1;
			for(int ba=i; ba>=1; ba--){
				if(val[ba][j] == 0) can = 0;
				int nw = way[j][i-ba+1]; // C(seg[j].se-seg[j].fi+1, i-ba+1)
				if(can){
					chsum(te, mul(sum(1, pr[ba-1][j-1]), nw) );
				}
			}

			dp[i][j] = sum(dp[i][j-1], te );
			pr[i][j] = sum(pr[i-1][j], dp[i][j]);
			// cout << dp[i][j] << ' '<< i << ' '<< j << " ij\n";
		}
	}

	cout << pr[n][k] << '\n';
} 
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...