oj.uz

Submission #554342

# Submission time Handle Problem Language Result Execution time Memory
554342 2022-04-28T07:46:02 Z Keshi Boat (APIO16_boat) C++17
0 / 100
 153 ms 8412 KB 
//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll maxn = 1024;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll pw(ll a, ll b){
	ll c = 1;
	while(b){
		if(b & 1) c = c * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return c;
}

int n, a[maxn], b[maxn];
ll pre[maxn][maxn];
vector<int> vec;
vector<pll> g[maxn];

int main(){
	fast_io;

	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		b[i]++;
		vec.pb(a[i]);
		vec.pb(b[i]);
	}
	vec.pb(0);
	sort(all(vec));
	vec.resize(unique(all(vec)) - vec.begin());
	for(int i = 0; i + 1 < Sz(vec); i++){
		g[i].pb({0, 0});
		int x = vec[i + 1] - vec[i] - 1;
		pre[i][0] = 1;
		for(int j = 1; j < maxn; j++){
			pre[i][j] = 1ll * pre[i][j - 1] * (x + j) % mod * pw(j, mod - 2) % mod;
		}
	}
	g[0].pb({1, 1});
	for(int i = 1; i <= n; i++){
		ll x = 0;
		for(int j = 0; j < Sz(vec) - 1; j++){
			if(vec[j] < a[i] || b[i] <= vec[j]){
				x += g[j].back().S;
				if(x >= mod) x -= mod;
				continue;
			}
			ll y = 1ll * x * pre[j][1] % mod;
			for(int k = 0; k < Sz(g[j]); k++){
				y = (y + 1ll * g[j][Sz(g[j]) - 1 - k].F * pre[j][k + 2]) % mod;
			}
			x += g[j].back().S;
			if(x >= mod) x -= mod;
			g[j].pb(Mp(x, y));
		}
	}
	int ans = 0;
	for(int i = 0; i < Sz(vec) - 1; i++){
		ans += g[i].back().S;
		if(ans >= mod) ans -= mod;
	}
	cout << (ans - 1 + mod) % mod << "\n";

	
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 8368 KB Output is correct
2 Correct 140 ms 8408 KB Output is correct
3 Correct 144 ms 8372 KB Output is correct
4 Correct 142 ms 8396 KB Output is correct
5 Correct 142 ms 8308 KB Output is correct
6 Correct 138 ms 8412 KB Output is correct
7 Correct 153 ms 8312 KB Output is correct
8 Correct 142 ms 8396 KB Output is correct
9 Correct 149 ms 8372 KB Output is correct
10 Correct 143 ms 8396 KB Output is correct
11 Correct 146 ms 8392 KB Output is correct
12 Correct 141 ms 8400 KB Output is correct
13 Correct 141 ms 8396 KB Output is correct
14 Correct 143 ms 8388 KB Output is correct
15 Correct 143 ms 8404 KB Output is correct
16 Incorrect 26 ms 1740 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 8368 KB Output is correct
2 Correct 140 ms 8408 KB Output is correct
3 Correct 144 ms 8372 KB Output is correct
4 Correct 142 ms 8396 KB Output is correct
5 Correct 142 ms 8308 KB Output is correct
6 Correct 138 ms 8412 KB Output is correct
7 Correct 153 ms 8312 KB Output is correct
8 Correct 142 ms 8396 KB Output is correct
9 Correct 149 ms 8372 KB Output is correct
10 Correct 143 ms 8396 KB Output is correct
11 Correct 146 ms 8392 KB Output is correct
12 Correct 141 ms 8400 KB Output is correct
13 Correct 141 ms 8396 KB Output is correct
14 Correct 143 ms 8388 KB Output is correct
15 Correct 143 ms 8404 KB Output is correct
16 Incorrect 26 ms 1740 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 8368 KB Output is correct
2 Correct 140 ms 8408 KB Output is correct
3 Correct 144 ms 8372 KB Output is correct
4 Correct 142 ms 8396 KB Output is correct
5 Correct 142 ms 8308 KB Output is correct
6 Correct 138 ms 8412 KB Output is correct
7 Correct 153 ms 8312 KB Output is correct
8 Correct 142 ms 8396 KB Output is correct
9 Correct 149 ms 8372 KB Output is correct
10 Correct 143 ms 8396 KB Output is correct
11 Correct 146 ms 8392 KB Output is correct
12 Correct 141 ms 8400 KB Output is correct
13 Correct 141 ms 8396 KB Output is correct
14 Correct 143 ms 8388 KB Output is correct
15 Correct 143 ms 8404 KB Output is correct
16 Incorrect 26 ms 1740 KB Output isn't correct
17 Halted 0 ms 0 KB -