oj.uz

Submission #795946

# Submission time Handle Problem Language Result Execution time Memory
795946 2023-07-28T00:21:55 Z bane Boat (APIO16_boat) C++17
9 / 100
 677 ms 15632 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 choose[m + 1][n + 1];
	ll inv[m + 1][n + 1];
	rep(i,m - 1){
		choose[i][1] = pts[i + 1] - pts[i]; 
		for(int j = 2; j <= n; j++){
			choose[i][j] = (choose[i][j - 1] * bpow(j, mod - 2) % mod) * (pts[i + 1] - pts[i] - j + 1) % mod;
		}
		rep1n(j,n){
			inv[i][j] = bpow(choose[i][j], mod - 2);
		}
	}
	ll orz[m + 1];
	memset(orz, 0, sizeof(orz));
	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)
				if (orz[j]){
					dp[i][j] += (dp[i - 1][j] * inv[j][orz[j]] % mod) * choose[j][orz[j] + 1] % mod;
					dp[i][j] %= mod;
				}
				orz[j]++;
				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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 12116 KB Output is correct
2 Correct 119 ms 12116 KB Output is correct
3 Correct 121 ms 12116 KB Output is correct
4 Correct 118 ms 12116 KB Output is correct
5 Correct 119 ms 12116 KB Output is correct
6 Correct 121 ms 12116 KB Output is correct
7 Correct 119 ms 12116 KB Output is correct
8 Correct 121 ms 12116 KB Output is correct
9 Correct 118 ms 12116 KB Output is correct
10 Correct 121 ms 12116 KB Output is correct
11 Correct 119 ms 12116 KB Output is correct
12 Correct 118 ms 12116 KB Output is correct
13 Correct 118 ms 12116 KB Output is correct
14 Correct 118 ms 12116 KB Output is correct
15 Correct 119 ms 12116 KB Output is correct
16 Correct 21 ms 2388 KB Output is correct
17 Correct 23 ms 2516 KB Output is correct
18 Correct 22 ms 2504 KB Output is correct
19 Correct 23 ms 2596 KB Output is correct
20 Correct 22 ms 2516 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 12116 KB Output is correct
2 Correct 119 ms 12116 KB Output is correct
3 Correct 121 ms 12116 KB Output is correct
4 Correct 118 ms 12116 KB Output is correct
5 Correct 119 ms 12116 KB Output is correct
6 Correct 121 ms 12116 KB Output is correct
7 Correct 119 ms 12116 KB Output is correct
8 Correct 121 ms 12116 KB Output is correct
9 Correct 118 ms 12116 KB Output is correct
10 Correct 121 ms 12116 KB Output is correct
11 Correct 119 ms 12116 KB Output is correct
12 Correct 118 ms 12116 KB Output is correct
13 Correct 118 ms 12116 KB Output is correct
14 Correct 118 ms 12116 KB Output is correct
15 Correct 119 ms 12116 KB Output is correct
16 Correct 21 ms 2388 KB Output is correct
17 Correct 23 ms 2516 KB Output is correct
18 Correct 22 ms 2504 KB Output is correct
19 Correct 23 ms 2596 KB Output is correct
20 Correct 22 ms 2516 KB Output is correct
21 Incorrect 677 ms 15632 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 12116 KB Output is correct
2 Correct 119 ms 12116 KB Output is correct
3 Correct 121 ms 12116 KB Output is correct
4 Correct 118 ms 12116 KB Output is correct
5 Correct 119 ms 12116 KB Output is correct
6 Correct 121 ms 12116 KB Output is correct
7 Correct 119 ms 12116 KB Output is correct
8 Correct 121 ms 12116 KB Output is correct
9 Correct 118 ms 12116 KB Output is correct
10 Correct 121 ms 12116 KB Output is correct
11 Correct 119 ms 12116 KB Output is correct
12 Correct 118 ms 12116 KB Output is correct
13 Correct 118 ms 12116 KB Output is correct
14 Correct 118 ms 12116 KB Output is correct
15 Correct 119 ms 12116 KB Output is correct
16 Correct 21 ms 2388 KB Output is correct
17 Correct 23 ms 2516 KB Output is correct
18 Correct 22 ms 2504 KB Output is correct
19 Correct 23 ms 2596 KB Output is correct
20 Correct 22 ms 2516 KB Output is correct
21 Incorrect 677 ms 15632 KB Output isn't correct
22 Halted 0 ms 0 KB -