Submission #1147219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147219		mertbbm	Boat (APIO16_boat)	C++20	58 / 100	2095 ms	7024 KiB

boat

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

unordered_map<int,int>mp[505];
int f2(int n, int k){
	if(n==0) return 0;
	if(mp[k].find(n)!=mp[k].end()) return mp[k][n];
 	int hold=1;
	for(int x=n;x<=n+k;x++){
		hold=(hold*x)%mod;
	}
	for(int x=1;x<=k+1;x++){
		hold=(hold*f(x,mod-2))%mod;
	}
	return mp[k][n]=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];
		}
	}
	
	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(); 
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42