Submission #403355

#TimeUsernameProblemLanguageResultExecution timeMemory
403355Bill_00Boat (APIO16_boat)C++14
9 / 100
622 ms16284 KiB
#include <bits/stdc++.h>
#define ll long long
const ll MOD=1000000007;
using namespace std;
ll n,k;
ll l[505],r[505],dp[505][1005],val[1005],cnt[505][1005],c[505][1005],sum[505][1005],len[1005];
unordered_map<ll,ll>um;
set<ll>s;
ll power(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1){
			res=res*x;
			if(res>=MOD) res%=MOD;
		}
		y>>=1;
		x=x*x;
		if(x>=MOD) x%=MOD;
	}
	return res;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(ll i=1;i<=n;i++){
		cin >> l[i] >> r[i];
		s.insert(l[i]);
		s.insert(r[i]+1);
	}
	for(auto i=s.begin();i!=s.end();++i){
		um[*i]=++k;
		val[k]=*i;
		if(k>1) len[k-1]=val[k]-val[k-1];
	}
	for(ll i=1;i<k;i++){
		c[i][0]=1;
		for(ll j=1;j<=n;j++){
			if(j>len[i]) sum[i][j]=sum[i][j-1];
			else{	
				c[i][j]=c[i][j-1]*(len[i]+1-j);
				if(c[i][j]>=MOD) c[i][j]%=MOD;
				c[i][j]*=power(j,MOD-2);
				if(c[i][j]>=MOD) c[i][j]%=MOD;
				sum[i][j]=sum[i][j-1]+c[i][j];
				if(sum[i][j]>=MOD) sum[i][j]%=MOD;
			}
			// cout << i << ' ' << j << ' ' << c[i][j] << '\n';
		}
	}
	for(int i=1;i<=k;i++){
		// cout << val[i] << ' ';
	}
	// cout << "\n";
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<k;j++){
			if(l[i]<=val[j] && val[j]<=r[i]){
				cnt[i][j]=cnt[i-1][j]+1;
			}
			else cnt[i][j]=cnt[i-1][j];
			// cout << i << ' ' << j << ' ' << cnt[i][j] << '\n';
		}
	}
	for(ll i=0;i<=n;i++){dp[i][0]=1;}
	for(ll i=0;i<=n;i++){
		for(ll j=1;j<k;j++){
			dp[i][j]+=dp[i][j-1];
			if(dp[i][j]>=MOD) dp[i][j]%=MOD;
			for(ll t=0;t<i;t++){
				if(val[j+1]<=l[t+1] || r[t+1]<val[j]) continue;
				ll p=cnt[i][j]-cnt[t][j];
				dp[i][j]+=(dp[t][j-1]*sum[j][p]);
				if(dp[i][j]>=MOD) dp[i][j]%=MOD;
				// if(i==1 && j==2) cout << cnt[i][j] << '\n';
			}
			// cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
		}
	}
	cout << (dp[n][k-1]-1+MOD)%MOD;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...