oj.uz

Submission #107005

# Submission time Handle Problem Language Result Execution time Memory
107005 2019-04-21T12:45:15 Z kek Boat (APIO16_boat) C++14
31 / 100
 2000 ms 214068 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);
	}
};

void run() {
	fenv t;
	t.plus(0, 1);
	// unordered_map<int, int> cur;
	// cur.rehash(1e7 + 100);
	// cur[0] = 1;
	int n;
	cin >> n;
	for (int kek = 0; kek < n; ++kek) {
		int a, b;
		cin >> a >> b;
		for (int i = b; i >= a; --i) {
			int s = t.get(i - 1);
			t.plus(i, s);
			// cur[i] = s;
		}
	}
	int ans = t.get(maxn - 20) - 1;
	if (ans < 0) {
		ans += mod;
	}
	assert(ans >= 0);
	cout << ans % mod << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 81656 KB Output is correct
2 Correct 90 ms 81532 KB Output is correct
3 Correct 105 ms 81532 KB Output is correct
4 Correct 108 ms 81500 KB Output is correct
5 Correct 98 ms 81528 KB Output is correct
6 Correct 98 ms 81528 KB Output is correct
7 Correct 102 ms 81400 KB Output is correct
8 Correct 109 ms 81592 KB Output is correct
9 Correct 106 ms 81528 KB Output is correct
10 Correct 81 ms 81524 KB Output is correct
11 Correct 91 ms 81544 KB Output is correct
12 Correct 89 ms 81528 KB Output is correct
13 Correct 105 ms 81536 KB Output is correct
14 Correct 89 ms 81528 KB Output is correct
15 Correct 103 ms 81532 KB Output is correct
16 Correct 94 ms 81364 KB Output is correct
17 Correct 87 ms 81404 KB Output is correct
18 Correct 104 ms 81400 KB Output is correct
19 Correct 99 ms 81384 KB Output is correct
20 Correct 99 ms 81400 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 81656 KB Output is correct
2 Correct 90 ms 81532 KB Output is correct
3 Correct 105 ms 81532 KB Output is correct
4 Correct 108 ms 81500 KB Output is correct
5 Correct 98 ms 81528 KB Output is correct
6 Correct 98 ms 81528 KB Output is correct
7 Correct 102 ms 81400 KB Output is correct
8 Correct 109 ms 81592 KB Output is correct
9 Correct 106 ms 81528 KB Output is correct
10 Correct 81 ms 81524 KB Output is correct
11 Correct 91 ms 81544 KB Output is correct
12 Correct 89 ms 81528 KB Output is correct
13 Correct 105 ms 81536 KB Output is correct
14 Correct 89 ms 81528 KB Output is correct
15 Correct 103 ms 81532 KB Output is correct
16 Correct 94 ms 81364 KB Output is correct
17 Correct 87 ms 81404 KB Output is correct
18 Correct 104 ms 81400 KB Output is correct
19 Correct 99 ms 81384 KB Output is correct
20 Correct 99 ms 81400 KB Output is correct
21 Correct 432 ms 81592 KB Output is correct
22 Correct 440 ms 81608 KB Output is correct
23 Correct 427 ms 81656 KB Output is correct
24 Correct 457 ms 81528 KB Output is correct
25 Correct 506 ms 81604 KB Output is correct
26 Correct 526 ms 81528 KB Output is correct
27 Correct 498 ms 81656 KB Output is correct
28 Correct 480 ms 81656 KB Output is correct
29 Correct 527 ms 81656 KB Output is correct
30 Correct 571 ms 112376 KB Output is correct
31 Correct 559 ms 111972 KB Output is correct
32 Correct 572 ms 112504 KB Output is correct
33 Correct 534 ms 111736 KB Output is correct
34 Correct 575 ms 111900 KB Output is correct
35 Correct 529 ms 110488 KB Output is correct
36 Correct 519 ms 111484 KB Output is correct
37 Correct 566 ms 111864 KB Output is correct
38 Correct 510 ms 110892 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 214068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 81656 KB Output is correct
2 Correct 90 ms 81532 KB Output is correct
3 Correct 105 ms 81532 KB Output is correct
4 Correct 108 ms 81500 KB Output is correct
5 Correct 98 ms 81528 KB Output is correct
6 Correct 98 ms 81528 KB Output is correct
7 Correct 102 ms 81400 KB Output is correct
8 Correct 109 ms 81592 KB Output is correct
9 Correct 106 ms 81528 KB Output is correct
10 Correct 81 ms 81524 KB Output is correct
11 Correct 91 ms 81544 KB Output is correct
12 Correct 89 ms 81528 KB Output is correct
13 Correct 105 ms 81536 KB Output is correct
14 Correct 89 ms 81528 KB Output is correct
15 Correct 103 ms 81532 KB Output is correct
16 Correct 94 ms 81364 KB Output is correct
17 Correct 87 ms 81404 KB Output is correct
18 Correct 104 ms 81400 KB Output is correct
19 Correct 99 ms 81384 KB Output is correct
20 Correct 99 ms 81400 KB Output is correct
21 Correct 432 ms 81592 KB Output is correct
22 Correct 440 ms 81608 KB Output is correct
23 Correct 427 ms 81656 KB Output is correct
24 Correct 457 ms 81528 KB Output is correct
25 Correct 506 ms 81604 KB Output is correct
26 Correct 526 ms 81528 KB Output is correct
27 Correct 498 ms 81656 KB Output is correct
28 Correct 480 ms 81656 KB Output is correct
29 Correct 527 ms 81656 KB Output is correct
30 Correct 571 ms 112376 KB Output is correct
31 Correct 559 ms 111972 KB Output is correct
32 Correct 572 ms 112504 KB Output is correct
33 Correct 534 ms 111736 KB Output is correct
34 Correct 575 ms 111900 KB Output is correct
35 Correct 529 ms 110488 KB Output is correct
36 Correct 519 ms 111484 KB Output is correct
37 Correct 566 ms 111864 KB Output is correct
38 Correct 510 ms 110892 KB Output is correct
39 Execution timed out 2029 ms 214068 KB Time limit exceeded
40 Halted 0 ms 0 KB -