답안 #107016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107016	2019-04-21T13:00:43 Z	maksim_gaponov	Boat (APIO16_boat)	C++14	31 / 100	2000 ms	107964 KB

boat

#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;
		sum %= MOD;
		for (; i < MAXN; i = ((i) | (i + 1))) {
			f[i] += x;
			f[i] %= MOD;
		}
	}

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

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
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	768 KB	Output is correct
2	Correct	5 ms	768 KB	Output is correct
3	Correct	4 ms	768 KB	Output is correct
4	Correct	4 ms	768 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	4 ms	768 KB	Output is correct
7	Correct	4 ms	768 KB	Output is correct
8	Correct	6 ms	768 KB	Output is correct
9	Correct	5 ms	768 KB	Output is correct
10	Correct	4 ms	796 KB	Output is correct
11	Correct	5 ms	768 KB	Output is correct
12	Correct	4 ms	764 KB	Output is correct
13	Correct	6 ms	768 KB	Output is correct
14	Correct	6 ms	768 KB	Output is correct
15	Correct	4 ms	768 KB	Output is correct
16	Correct	3 ms	512 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	3 ms	512 KB	Output is correct
19	Correct	3 ms	512 KB	Output is correct
20	Correct	3 ms	512 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	768 KB	Output is correct
2	Correct	5 ms	768 KB	Output is correct
3	Correct	4 ms	768 KB	Output is correct
4	Correct	4 ms	768 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	4 ms	768 KB	Output is correct
7	Correct	4 ms	768 KB	Output is correct
8	Correct	6 ms	768 KB	Output is correct
9	Correct	5 ms	768 KB	Output is correct
10	Correct	4 ms	796 KB	Output is correct
11	Correct	5 ms	768 KB	Output is correct
12	Correct	4 ms	764 KB	Output is correct
13	Correct	6 ms	768 KB	Output is correct
14	Correct	6 ms	768 KB	Output is correct
15	Correct	4 ms	768 KB	Output is correct
16	Correct	3 ms	512 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	3 ms	512 KB	Output is correct
19	Correct	3 ms	512 KB	Output is correct
20	Correct	3 ms	512 KB	Output is correct
21	Correct	924 ms	724 KB	Output is correct
22	Correct	950 ms	860 KB	Output is correct
23	Correct	837 ms	632 KB	Output is correct
24	Correct	938 ms	636 KB	Output is correct
25	Correct	913 ms	632 KB	Output is correct
26	Correct	950 ms	512 KB	Output is correct
27	Correct	925 ms	548 KB	Output is correct
28	Correct	826 ms	512 KB	Output is correct
29	Correct	869 ms	588 KB	Output is correct
30	Correct	840 ms	50108 KB	Output is correct
31	Correct	916 ms	50152 KB	Output is correct
32	Correct	1031 ms	50140 KB	Output is correct
33	Correct	987 ms	50156 KB	Output is correct
34	Correct	877 ms	50088 KB	Output is correct
35	Correct	925 ms	50280 KB	Output is correct
36	Correct	1131 ms	50072 KB	Output is correct
37	Correct	1113 ms	50080 KB	Output is correct
38	Correct	1018 ms	49992 KB	Output is correct

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2037 ms	107964 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	768 KB	Output is correct
2	Correct	5 ms	768 KB	Output is correct
3	Correct	4 ms	768 KB	Output is correct
4	Correct	4 ms	768 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	4 ms	768 KB	Output is correct
7	Correct	4 ms	768 KB	Output is correct
8	Correct	6 ms	768 KB	Output is correct
9	Correct	5 ms	768 KB	Output is correct
10	Correct	4 ms	796 KB	Output is correct
11	Correct	5 ms	768 KB	Output is correct
12	Correct	4 ms	764 KB	Output is correct
13	Correct	6 ms	768 KB	Output is correct
14	Correct	6 ms	768 KB	Output is correct
15	Correct	4 ms	768 KB	Output is correct
16	Correct	3 ms	512 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	3 ms	512 KB	Output is correct
19	Correct	3 ms	512 KB	Output is correct
20	Correct	3 ms	512 KB	Output is correct
21	Correct	924 ms	724 KB	Output is correct
22	Correct	950 ms	860 KB	Output is correct
23	Correct	837 ms	632 KB	Output is correct
24	Correct	938 ms	636 KB	Output is correct
25	Correct	913 ms	632 KB	Output is correct
26	Correct	950 ms	512 KB	Output is correct
27	Correct	925 ms	548 KB	Output is correct
28	Correct	826 ms	512 KB	Output is correct
29	Correct	869 ms	588 KB	Output is correct
30	Correct	840 ms	50108 KB	Output is correct
31	Correct	916 ms	50152 KB	Output is correct
32	Correct	1031 ms	50140 KB	Output is correct
33	Correct	987 ms	50156 KB	Output is correct
34	Correct	877 ms	50088 KB	Output is correct
35	Correct	925 ms	50280 KB	Output is correct
36	Correct	1131 ms	50072 KB	Output is correct
37	Correct	1113 ms	50080 KB	Output is correct
38	Correct	1018 ms	49992 KB	Output is correct
39	Execution timed out	2037 ms	107964 KB	Time limit exceeded
40	Halted	0 ms	0 KB	-

답안 #107016

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
0 / 27.0

Subtask #4
0 / 42.0