Submission #1147212

#TimeUsernameProblemLanguageResultExecution timeMemory
1147212mertbbmBoat (APIO16_boat)C++20
9 / 100
147 ms4920 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

const int mod=1e9+7;
int f(int a, int b){
	if(a==1||b==0) return 1;
	if(b==1) return a;
	int hold=f((a*a)%mod,b/2);
	if(b%2) hold=(hold*a)%mod;
	return hold; 
}

int fac[1005];
int memo[505][505];

int f2(int n, int k){
	if(n==0) return 0;
	if(memo[n][k]!=-1) return memo[n][k];
 	int hold=fac[n+k];
	int hold2=f(fac[n-1],mod-2);
	int hold3=f(fac[k+1],mod-2);
	hold=(hold*hold2)%mod;
	hold=(hold*hold3)%mod;
	return memo[n][k]=hold;
}

void solve(){
	int n;
	cin >> n;
	pii arr[n];
	vector<int>v;
	for(int x=0;x<n;x++){
		cin >> arr[x].first >> arr[x].second;
		v.push_back(arr[x].first);
		v.push_back(arr[x].second+1);
	}
	
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());
	
	vector<int>storage[2*n+5];
	int len[2*n+5];
	for(int x=0;x<(int)v.size()-1;x++){
		len[x]=v[x+1]-v[x];
	}

	for(int x=0;x<n;x++){
		int cur=arr[x].first;
		
		while(cur<=arr[x].second){
			int index=upper_bound(v.begin(),v.end(),cur)-v.begin();
			storage[index-1].push_back(x);
			cur=v[index];
		}
	}
	
	fac[0]=1;
	for(int x=1;x<1000;x++){
		fac[x]=(fac[x-1]*x)%mod;
	}
	memset(memo,-1,sizeof(memo));
	
	int ans=0;
	int cnt[n];
	memset(cnt,0,sizeof(cnt));
	for(int x=0;x<(int)v.size();x++){
		int prefix[n];
		memset(prefix,0,sizeof(prefix));
		prefix[0]=cnt[0];
		for(int y=1;y<n;y++){
			prefix[y]=(cnt[y]+prefix[y-1])%mod;
		}
		
		int sz=storage[x].size();
		int add[n];
		memset(add,0,sizeof(add));
		for(int y=0;y<sz;y++){
			int counter=0;
			for(int i=0;i<=y;i++){
				int val;
				if(y==i) val=len[x];
				else val=f2(len[x]-1,y-i);
				int multi=0;
				if(storage[x][i]>0) multi=prefix[storage[x][i]-1];
				int hold=(multi*val)%mod;
				counter=(counter+hold)%mod;
			}
			int hold=f2(len[x],y);
			counter=(counter+hold)%mod;
			add[storage[x][y]]=(add[storage[x][y]]+counter)%mod;
			ans=(ans+counter)%mod;
		}
		
		for(int y=0;y<n;y++){
			cnt[y]=(cnt[y]+add[y])%mod;
		}
	}
	
	cout << ans;
	
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("in.txt","w",stdout);
	int t=1;	        
	//cin >> t;	
	while(t--){
		solve(); 
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...