제출 #1340886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1340886		javkhlantogs	Boat (APIO16_boat)	C++20	9 / 100	83 ms	5700 KiB

boat

#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++){                                                                                                     
		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=1 ; j<cnt ; j++) if(i>0) dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;                                                                                                                                                  
		for(j=1 ; j<cnt ; j++) update(0,cnt-1,1,j,dp[i][j]);                                  
	}                                                                                    
	ll ans=query(0,cnt-1,1,0,cnt-1)-1;	                               
	cout<<ans;                                                                    
	return 0;                                                                 
}                                                                         

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