Submission #1340877

#TimeUsernameProblemLanguageResultExecution timeMemory
1340877javkhlantogsBoat (APIO16_boat)C++20
0 / 100
34 ms4420 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll mod=1e9+7;
vector<ll> t;
void update(ll tl,ll tr,ll v,ll pos,ll val){
	if(tl==tr) t[v]=val;
		else{
			ll tm=(tl+tr)/2;
			if(pos<=tm) update(tl,tm,2*v,pos,val);
				else update(tm+1,tr,2*v+1,pos,val);
			t[v]=(t[2*v]+t[2*v+1])%mod;
		}
}
ll query(ll tl,ll tr,ll v,ll l,ll r){
	if(tl>r or l>tr) return 0;
	if(l<=tl and tr<=r) return t[v];
	ll tm=(tl+tr)/2;
	return (query(tl,tm,2*v,l,r)+query(tm+1,tr,2*v+1,l,r))%mod;
}
int main(){
	ll n,i,j,k,q;
	cin>>n;
	vector<ll> a(n),b(n);
	for(i=0 ; i<n ; i++) cin>>a[i]>>b[i];
	map<ll,ll> mp,mp1;
	for(i=0 ; i<n ; i++){
		mp[a[i]]++;
		mp[b[i]]++;
		mp[b[i]+1]++;
	}
	ll cnt=1;
	for(auto v:mp){
		mp[v.first]=cnt;
		mp1[cnt++]=v.first;
	}
	t.resize(4*cnt,0);
	update(0,cnt-1,1,0,1);
	vector<vector<ll>> dp(n,vector<ll>(cnt+1,0));
	dp[0][0]=1;
	for(i=0 ; i<n ; i++){
		dp[i][0]=query(0,cnt-1,1,0,cnt-1);
		for(j=mp[a[i]] ; j<=mp[b[i]] ; j++){
			ll length;
			if(j==mp[a[i]]) length=1;
				else length=mp1[j]-mp1[j-1];
			ll val=(query(0,cnt-1,1,0,j-1)*length)%mod;
			dp[i][j]=val;
		}
		for(j=0 ; j<cnt ; j++) update(0,cnt-1,1,j,dp[i][j]);
	}
	ll ans=(query(0,cnt-1,1,0,cnt-1)-1+mod)%mod;	
	cout<<ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...