Submission #253697

#	Time	Username	Problem	Language	Result	Execution time	Memory
253697		errorgorn	Boat (APIO16_boat)	C++14	100 / 100	1488 ms	8576 KiB

boat

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MOD=1000000007;

ll qexp(ll b,ll p,int m){
    ll res=1;
    while (p){
        if (p&1) res=(res*b)%m;
        b=(b*b)%m;
        p>>=1;
    }
    return res;
}

ll inv(ll i){
	return qexp(i,MOD-2,MOD);
}


int n;
ii range[505];
vector<int> pos={0,1};

ll cnt[1005][505];
ll memo[1005][505];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	rep(x,0,n){
		cin>>range[x].fi>>range[x].se;
		pos.push_back(range[x].fi);
		pos.push_back(range[x].se+1);
	}
	
	sort(all(pos));
	pos.erase(unique(all(pos)),pos.end());
	
	rep(x,0,sz(pos)-1){
		int val=pos[x+1]-pos[x];
		
		cnt[x][0]=val;
		rep(y,1,min(val,505)){
			cnt[x][y]=cnt[x][y-1]*(val-y)%MOD*inv(y+1)%MOD;
		}
	}
	
	//for (auto &it:pos) cout<<it<<" ";cout<<endl;
	
	memo[0][0]=1;
	
	ll curr;
	rep(z,0,n){
		curr=0;
		rep(x,0,sz(pos)-1){
			ll temp=curr;
			
			rep(y,0,505) curr=(curr+cnt[x][y]*memo[x][y])%MOD;
			if (range[z].fi<=pos[x] && pos[x]<=range[z].se){
				rep(y,505,1) memo[x][y]=(memo[x][y]+memo[x][y-1])%MOD;
				memo[x][0]=(memo[x][0]+temp)%MOD;
			}
			//cout<<curr<<endl;
		}
		
		/*
		rep(x,0,sz(pos)-1){
			rep(y,0,4) cout<<memo[x][y]<<" ";
			cout<<endl;
		}
		cout<<endl;
		//*/
	}
	
	curr=0;
	rep(x,1,sz(pos)-1){
		rep(y,0,505) curr=(curr+cnt[x][y]*memo[x][y])%MOD;
	}
	cout<<curr<<endl;
}

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