제출 #1340869

#제출 시각아이디문제언어결과실행 시간메모리
1340869javkhlantogsBoat (APIO16_boat)C++20
0 / 100
22 ms496 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]]++;
	}
	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);
	for(i=0 ; i<n ; i++){
		ll vals=query(0,cnt-1,1,0,cnt-1);
		for(j=mp[b[i]] ; j>=mp[a[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;
			update(0,cnt-1,1,j,val);
		}
		for(j=1 ; j<cnt ; j++){
			if(a[i]>mp1[j] or mp1[j-1]+1>b[i]) update(0,cnt-1,1,j,0);
		}
		update(0,cnt-1,1,0,vals);
	}
	ll ans=(query(0,cnt-1,1,0,cnt-1)-1+mod)%mod;
	cout<<ans<<"\n";
	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...