oj.uz

Submission #107023

# Submission time Handle Problem Language Result Execution time Memory
107023 2019-04-21T13:29:04 Z kek Boat (APIO16_boat) C++14
9 / 100
 445 ms 8448 KB 
// #include "gap.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define all(v) v.begin(), v.end()
#define len(v) ((int)(v).size())
#define pb push_back
#define kek pop_back
#define pii pair<int, int>
#define mp make_pair

#define debug(x) cout << #x << " = " << x << endl;

const int INF = 1e18 + 666;

template<class t1, class t2>
bool cmin(t1 &a, const t2 &b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template<class t1, class t2>
bool cmax(t1 &a, const t2 &b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

// void MinMax(ll, ll, ll*, ll*);

// ll firstGroup(int);
// ll secondGroup(int);

// ll calc_ans(vector<ll> a) {
// 	sort(all(a));
// 	ll ans = 0;
// 	for (int i = 0; i + 1 < len(a); ++i) {
// 		cmax(ans, a[i + 1] - a[i]);
// 	}
// 	return ans;
// }

// ll findGap(int t, int n) {
// 	if (t == 1) {
// 		return firstGroup(n);
// 	} else {
// 		return secondGroup(n);
// 	}
// }

// ll firstGroup(int n) {
// 	vector<ll> a;
// 	ll l = 0, r = 1e18;
// 	while (len(a) < n) {
// 		MinMax(l, r, &l, &r);
// 		if (l == -1) {
// 			break;
// 		}
// 		a.pb(l);
// 		if (l != r) {
// 			a.pb(r);
// 		}
// 		++l;
// 		--r;
// 	}
// 	return calc_ans(a);
// }

// vector<ll> restore(ll l, ll r) {
// 	if (l > r) {
// 		return {};
// 	}
// 	MinMax(l, r, &l, &r);
// 	if (l == -1) {
// 		return {};
// 	}
// 	if (l == r) {
// 		return {l};
// 	}
// 	ll m = (l + r) >> 1;
// 	vector<ll> ans = {l, r};
// 	for (auto &x : restore(l + 1, m)) {
// 		ans.pb(x);
// 	}
// 	for (auto &x : restore(m + 1, r - 1)) {
// 		ans.pb(x);
// 	}
// 	return ans;
// }

// ll secondGroup(int n) {
// 	return calc_ans(restore(0, 1e18));
// }

void run();

signed main() {
	iostream::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
}

const int mod = 1e9 + 7;
// const int maxn = 1e9 + 100;

// struct fenv {
// 	unordered_map<int, int> tree;
// 	// int maxn;

// 	fenv() {
// 		tree.rehash(1e7 + 100);
// 	}

// 	int get(int i) {
// 		++i;
// 		int sm = 0;
// 		for (; i > 0; i -= f(i)) {
// 			auto it = tree.find(i);
// 			if (it != tree.end()) {
// 				sm += it->second;
// 				if (sm >= mod) {
// 					sm -= mod;
// 				}
// 			}
// 		}
// 		return sm;
// 	}

// 	void plus(int i, int v) {
// 		++i;
// 		for (; i < maxn; i += f(i)) {
// 			int &cur = tree[i];
// 			cur += v;
// 			// if (cur < 0) {
// 			// 	cur += mod;
// 			// }
// 			if (cur >= mod) {
// 				cur -= mod;
// 			}
// 		}
// 	}

// 	int f(int i) {
// 		return i & (-i);
// 	}
// };

int pow(int a, int b, int m) {
	int res = 1;
	for (; b > 0; b >>= 1) {
		if (b & 1) {
			res *= a;
			res %= m;
		}
		a *= a;
		a %= m;
	}
	return res;
}

pair<vector<int>, vector<pii>> make_kek(const vector<pii> &v) {
	vector<int> points;
	points.pb(0);
	points.pb(1);
	for (auto &x : v) {
		points.pb(x.first);
		points.pb(x.second + 1);
	}
	sort(all(points));
	points.resize(unique(all(points)) - points.begin());
	vector<int> lens;
	for (int i = 0; i + 1 < len(points); ++i) {
		lens.pb(points[i + 1] - points[i]);
	}
	vector<pii> ans;
	for (auto &x : v) {
		int l = lower_bound(all(points), x.first) - points.begin();
		int r = upper_bound(all(points), x.second) - points.begin();
		ans.pb({l, r - 1});
	}
	return {lens, ans};
}

void update(vector<int> &r, int &s, const vector<int> &c) {
	for (int i = len(r) - 1; i > 0; --i) {
		r[i] += r[i - 1];
		s += (r[i - 1] * c[i + 1]) % mod;
		if (r[i] >= mod) {
			r[i] -= mod;
		}
		if (s >= mod) {
			s -= mod;
		}
	}
}

void run() {
	int n;
	cin >> n;
	vector<int> rev(n + 1, 0);
	rev[1] = 1;
	for (int i = 2; i < n + 1; ++i) {
		rev[i] = mod - ((mod / i) * rev[mod % i]) % mod;
	}
	vector<pii> v(n);
	for (auto &x : v) {
		cin >> x.first >> x.second;
	}
	vector<int> lens;
	tie(lens, v) = make_kek(v);
	int m = len(lens);
	vector<vector<int>> C(m, vector<int>(n + 1));
	for (int i = 0; i < m; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= n; ++j) {
			C[i][j] = (C[i][j - 1] * (lens[i] - j + 1)) % mod;
			C[i][j] = (C[i][j] * rev[j]) % mod;
		}
	}
	vector<vector<int>> dp(m, vector<int>(n, 0));
	vector<int> sm(m, 0);
	dp[0][0] = 1;
	sm[0] = 1;
	for (auto &x : v) {
		int psm = 0;
		for (int i = 0; i <= x.second; ++i) {
			psm += sm[i];
		}
		psm %= mod;
		for (int i = x.second; i >= x.first; --i) {
			psm -= sm[i];
			if (psm < 0) {
				psm += mod;
			}
			dp[i][0] += psm;
			sm[i] += (psm * lens[i]) % mod;
			update(dp[i], sm[i], C[i]);
		}
	}
	int ans = accumulate(all(sm), 0ll) - 1;
	cout << ans % mod << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8320 KB Output is correct
2 Correct 17 ms 8320 KB Output is correct
3 Correct 18 ms 8320 KB Output is correct
4 Correct 16 ms 8320 KB Output is correct
5 Correct 19 ms 8368 KB Output is correct
6 Correct 17 ms 8320 KB Output is correct
7 Correct 19 ms 8320 KB Output is correct
8 Correct 19 ms 8336 KB Output is correct
9 Correct 18 ms 8448 KB Output is correct
10 Correct 18 ms 8340 KB Output is correct
11 Correct 18 ms 8448 KB Output is correct
12 Correct 18 ms 8320 KB Output is correct
13 Correct 21 ms 8320 KB Output is correct
14 Correct 17 ms 8316 KB Output is correct
15 Correct 17 ms 8320 KB Output is correct
16 Correct 5 ms 1792 KB Output is correct
17 Correct 6 ms 1920 KB Output is correct
18 Correct 7 ms 1792 KB Output is correct
19 Correct 7 ms 1920 KB Output is correct
20 Correct 6 ms 1792 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8320 KB Output is correct
2 Correct 17 ms 8320 KB Output is correct
3 Correct 18 ms 8320 KB Output is correct
4 Correct 16 ms 8320 KB Output is correct
5 Correct 19 ms 8368 KB Output is correct
6 Correct 17 ms 8320 KB Output is correct
7 Correct 19 ms 8320 KB Output is correct
8 Correct 19 ms 8336 KB Output is correct
9 Correct 18 ms 8448 KB Output is correct
10 Correct 18 ms 8340 KB Output is correct
11 Correct 18 ms 8448 KB Output is correct
12 Correct 18 ms 8320 KB Output is correct
13 Correct 21 ms 8320 KB Output is correct
14 Correct 17 ms 8316 KB Output is correct
15 Correct 17 ms 8320 KB Output is correct
16 Correct 5 ms 1792 KB Output is correct
17 Correct 6 ms 1920 KB Output is correct
18 Correct 7 ms 1792 KB Output is correct
19 Correct 7 ms 1920 KB Output is correct
20 Correct 6 ms 1792 KB Output is correct
21 Incorrect 445 ms 7632 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8320 KB Output is correct
2 Correct 17 ms 8320 KB Output is correct
3 Correct 18 ms 8320 KB Output is correct
4 Correct 16 ms 8320 KB Output is correct
5 Correct 19 ms 8368 KB Output is correct
6 Correct 17 ms 8320 KB Output is correct
7 Correct 19 ms 8320 KB Output is correct
8 Correct 19 ms 8336 KB Output is correct
9 Correct 18 ms 8448 KB Output is correct
10 Correct 18 ms 8340 KB Output is correct
11 Correct 18 ms 8448 KB Output is correct
12 Correct 18 ms 8320 KB Output is correct
13 Correct 21 ms 8320 KB Output is correct
14 Correct 17 ms 8316 KB Output is correct
15 Correct 17 ms 8320 KB Output is correct
16 Correct 5 ms 1792 KB Output is correct
17 Correct 6 ms 1920 KB Output is correct
18 Correct 7 ms 1792 KB Output is correct
19 Correct 7 ms 1920 KB Output is correct
20 Correct 6 ms 1792 KB Output is correct
21 Incorrect 445 ms 7632 KB Output isn't correct
22 Halted 0 ms 0 KB -