Submission #1368958

#TimeUsernameProblemLanguageResultExecution timeMemory
1368958ByeWorldBoat (APIO16_boat)C++20
100 / 100
1137 ms16336 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], le[MAXN], ri[MAXN], dp[MAXN][MAXN], pr[MAXN];
int inv[MAXN], pre[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++){
		le[i] = -1;
		for(int j=1; j<=k; j++){
			if(l[i]<=seg[j].fi && seg[j].se<=r[i]){
				if(le[i] == -1) le[i] = j;
				ri[i] = j;
			}
		}
	}

	inv[0] = 1;
	for(int i=1; i<=n; i++){
		inv[i] = expo(i, MOD-2);
	}
	
	// for(auto [x,y] : seg) cout << x <<  ' ' << y << " y\n";
	dp[0][0] = pre[0][0] = 1;
	for(int i=0; i<=k; i++) pr[i] = 1;

	for(int i=1; i<=n; i++){
		for(int j=le[i]; j<=ri[i]; j++){
			// dp[i][j]
			int len = seg[j].se-seg[j].fi+1;
			chsum(dp[j][1], mul(len, pr[j-1]) );

			for(int num=2; num<=i; num++){
				// dp[j][num]
				int te = mul(pre[j][num-1], (len-num+1));
				chmul(te, inv[num]);
				chsum(dp[j][num], te);
			}
			// cout << dp[j][num] << ' '<< j << ' '<< num << " ij\n";
		}
		for(int j=0; j<=k; j++) 
			for(int num=0; num<=n; num++) pre[j][num] = dp[j][num];

		for(int j=1; j<=k; j++){
			pr[j] = pr[j-1];
			for(int num=0; num<=n; num++) chsum(pr[j], dp[j][num]);
		}
	}

	cout << pr[k]-1 << '\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...