Submission #795945

# Submission time Handle Problem Language Result Execution time Memory
795945 2023-07-28T00:03:26 Z bane Boat (APIO16_boat) C++17
9 / 100
529 ms 5428 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 4 ms 4276 KB Output is correct
3 Correct 4 ms 4180 KB Output is correct
4 Correct 4 ms 4276 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 4 ms 4180 KB Output is correct
7 Correct 4 ms 4180 KB Output is correct
8 Correct 4 ms 4180 KB Output is correct
9 Correct 3 ms 4180 KB Output is correct
10 Correct 4 ms 4180 KB Output is correct
11 Correct 4 ms 4180 KB Output is correct
12 Correct 4 ms 4272 KB Output is correct
13 Correct 4 ms 4180 KB Output is correct
14 Correct 4 ms 4180 KB Output is correct
15 Correct 4 ms 4180 KB Output is correct
16 Correct 1 ms 980 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 980 KB Output is correct
20 Correct 1 ms 980 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 4 ms 4276 KB Output is correct
3 Correct 4 ms 4180 KB Output is correct
4 Correct 4 ms 4276 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 4 ms 4180 KB Output is correct
7 Correct 4 ms 4180 KB Output is correct
8 Correct 4 ms 4180 KB Output is correct
9 Correct 3 ms 4180 KB Output is correct
10 Correct 4 ms 4180 KB Output is correct
11 Correct 4 ms 4180 KB Output is correct
12 Correct 4 ms 4272 KB Output is correct
13 Correct 4 ms 4180 KB Output is correct
14 Correct 4 ms 4180 KB Output is correct
15 Correct 4 ms 4180 KB Output is correct
16 Correct 1 ms 980 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 980 KB Output is correct
20 Correct 1 ms 980 KB Output is correct
21 Incorrect 529 ms 5428 KB Output isn't correct
22 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 4 ms 4276 KB Output is correct
3 Correct 4 ms 4180 KB Output is correct
4 Correct 4 ms 4276 KB Output is correct
5 Correct 3 ms 4180 KB Output is correct
6 Correct 4 ms 4180 KB Output is correct
7 Correct 4 ms 4180 KB Output is correct
8 Correct 4 ms 4180 KB Output is correct
9 Correct 3 ms 4180 KB Output is correct
10 Correct 4 ms 4180 KB Output is correct
11 Correct 4 ms 4180 KB Output is correct
12 Correct 4 ms 4272 KB Output is correct
13 Correct 4 ms 4180 KB Output is correct
14 Correct 4 ms 4180 KB Output is correct
15 Correct 4 ms 4180 KB Output is correct
16 Correct 1 ms 980 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 980 KB Output is correct
20 Correct 1 ms 980 KB Output is correct
21 Incorrect 529 ms 5428 KB Output isn't correct
22 Halted 0 ms 0 KB -