oj.uz

Submission #107015

# Submission time Handle Problem Language Result Execution time Memory
107015 2019-04-21T12:59:44 Z maksim_gaponov Boat (APIO16_boat) C++14
0 / 100
 2000 ms 136288 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

const int MOD = 1e9 + 7;

int mod(int x) {
	x %= MOD;
	if (x < 0)
		x += MOD;
	return x;
}

const int MAXN = 1e9 + 10;

struct ST {
	unordered_map<int, int> f;
	int sum = 0;

	void add(int i, int x) {
		sum += x;
		for (; i < MAXN; i = ((i) | (i + 1)))
			f[i] += x;
	}

	int get(int r) {
		--r;
		int res = 0;
		for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
			res += f[i];
		return res;
	}
};

void run() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		// assert(a[i] == b[i]);
	}
	ST S;
	S.add(0, 1);
	for (int i = 0; i < n; ++i) {
		for (int j = b[i]; j >= a[i]; --j) {
			S.add(j, S.get(j));
		}
	}
	// vector<vector<int>> dp(n);
	// vector<int> dp0(n);
	// for (int i = 0; i < n; ++i) {
	// 	if (i == 0)
	// 		dp0[i] = 1;
	// 	else
	// 		dp0[i] = dp[i - 1].back();
	// 	dp[i].resize(b[i] - a[i] + 1);
	// 	for (int j = a[i]; j <= b[i]; ++j) {
	// 		dp[i][j - a[i]] = 1;
	// 		if (j != a[i]) {
	// 			dp[i][j - a[i]] += dp[i][j - a[i] - 1];
	// 		} else {
	// 			dp[i][j - a[i]] += dp0[i];
	// 		}
	// 		// if (i > 0) {
	// 		// 	dp[i][j - a[i]] += dp[i - 1][j - 1 - a[i - 1]]
	// 		// }
	// 		if (i > 0) {
	// 			int val = 0;
	// 			if (j - 1 >= a[i - 1]) {
	// 				if (j - 1 > b[i - 1])
	// 					val = dp[i - 1].back();
	// 				else
	// 					val = dp[i - 1][j - a[i - 1] - 1];
	// 			}
	// 			else {
	// 				val = dp0[i - 1];
	// 			}
	// 			dp[i][j - a[i]] += val;
	// 		} else {
	// 			dp[i][j - a[i]] += 1;
	// 		}
	// 		dp[i][j - a[i]] %= MOD;
	// 	}
	// }
	int ans = S.sum;
	ans--;
	ans = mod(ans);
	cout << ans << '\n';
}

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Incorrect 4 ms 768 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Incorrect 4 ms 768 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Incorrect 4 ms 768 KB Output isn't correct
7 Halted 0 ms 0 KB -