Submission #795945

#	Time	Username	Problem	Language	Result	Execution time	Memory
795945		bane	Boat (APIO16_boat)	C++17	9 / 100	529 ms	5428 KiB

boat

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/


#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)


#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'

 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
 
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

const int nax = (int)501;
const int mod = (int)1e9 + 7;

int a[nax], b[nax];

ll bpow(ll a, ll b){
	ll res = 1;
	while(b){
		if (b & 1)
			res = (a * res) % mod;
		b /= 2;
		a = (a * a) % mod;
	}
	return res;
}


ll O = bpow(2,mod - 2);

ll c (ll a){
	return (((a * (a - 1))%mod) * O)%mod;
}

void solve(){
	int n;
	cin >> n;
	vector<int>pts;	
	rep1n(i,n){
		cin >> a[i] >> b[i];
		pts.pb(a[i]);
		pts.pb(b[i]);
		pts.pb(b[i] + 1);
	}
	pts.push_back(0);
	sort(all(pts));
	pts.erase(unique(all(pts)), pts.end());
	int m = pts.size();
	ll dp[n + 1][m + 1];
	memset(dp, 0LL, sizeof(dp));
	dp[0][0] = 1;
	ll inv[m + 1];
	rep(i,m - 1){
		inv[i] = bpow(pts[i + 1] - pts[i], mod - 2);
	}
	rep1n(i,n){
		rep(j,m){
			dp[i][j] = dp[i - 1][j];
			//cout << dp[i][j] << " ";
		}
		cout << endl;
		rep(j,m - 1){
			if (a[i] <= pts[j] && pts[j + 1] <= b[i] + 1){
				//in range [L, R)

				dp[i][j] += (dp[i - 1][j] * inv[j] % mod) * c(pts[j + 1] - pts[j]) % mod;
				dp[i][j] %= mod;

				repr(k,j){
					//dp[i-1][k]
					dp[i][j] += dp[i - 1][k] * (pts[j + 1] - pts[j]) % mod;
					dp[i][j] %= mod;
				}
			}
		}
	}
	
	ll ans = 0;
	rep1n(i,m-1){
		//cout << dp[n][i] << endl;
		ans += dp[n][i];
		ans %= mod;
	}
	cout << ans << '\n';
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);	
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
	return 0;
}

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