Submission #733004

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
733004	2023-04-30T02:04:46 Z	SanguineChameleon	Boat (APIO16_boat)	C++17	0 / 100	102 ms	468 KB

boat

#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxn = 5e2 + 20;
const long long mod = 1e9 + 7;
bool flag[maxn];
long long cur[maxn];
long long nxt[maxn];
pair<int, int> events[maxn * 2];
int n;

void trans() {
	for (int i = 1; i <= n; i++) {
		nxt[i] = cur[i];
		if (flag[i]) {
			nxt[i] = (nxt[i] + 1) % mod;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (flag[j]) {
				nxt[j] = (nxt[j] + cur[i]) % mod;
			}
		}
	}
	swap(cur, nxt);
}

void just_do_it() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		events[i * 2 - 1] = make_pair(a, i);
		events[i * 2] = make_pair(b + 1, -i);
	}
	sort(events + 1, events + n * 2 + 1);
	int cur_t = 0;
	for (int i = 1; i <= n * 2; i++) {
		int nxt_t = events[i].first;
		int id = events[i].second;
		bool end = (i == n * 2 || events[i].first != events[i + 1].first);
		if (end) {
			if (cur_t < nxt_t - 1) {
				for (int i = 1; i <= n; i++) {
					assert(!flag[i]);
				}
				cur_t = nxt_t - 1;
			}
		}
		if (id > 0) {
			flag[id] = true;
		}
		else {
			flag[-id] = false;
		}
		if (end && cur_t == nxt_t - 1) {
			trans();
			cur_t = nxt_t;
		}
	}
	long long res = 0;
	for (int i = 1; i <= n; i++) {
		res += cur[i];
		res %= mod;
	}
	cout << res;
}

Subtask #1

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	212 KB	Output is correct
2	Correct	94 ms	212 KB	Output is correct
3	Correct	101 ms	340 KB	Output is correct
4	Correct	102 ms	316 KB	Output is correct
5	Correct	95 ms	316 KB	Output is correct
6	Correct	90 ms	312 KB	Output is correct
7	Correct	92 ms	212 KB	Output is correct
8	Correct	95 ms	320 KB	Output is correct
9	Correct	95 ms	316 KB	Output is correct
10	Correct	95 ms	212 KB	Output is correct
11	Correct	93 ms	320 KB	Output is correct
12	Correct	90 ms	316 KB	Output is correct
13	Correct	96 ms	312 KB	Output is correct
14	Correct	93 ms	316 KB	Output is correct
15	Correct	99 ms	320 KB	Output is correct
16	Runtime error	1 ms	468 KB	Execution killed with signal 6
17	Halted	0 ms	0 KB	-

Subtask #2

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	212 KB	Output is correct
2	Correct	94 ms	212 KB	Output is correct
3	Correct	101 ms	340 KB	Output is correct
4	Correct	102 ms	316 KB	Output is correct
5	Correct	95 ms	316 KB	Output is correct
6	Correct	90 ms	312 KB	Output is correct
7	Correct	92 ms	212 KB	Output is correct
8	Correct	95 ms	320 KB	Output is correct
9	Correct	95 ms	316 KB	Output is correct
10	Correct	95 ms	212 KB	Output is correct
11	Correct	93 ms	320 KB	Output is correct
12	Correct	90 ms	316 KB	Output is correct
13	Correct	96 ms	312 KB	Output is correct
14	Correct	93 ms	316 KB	Output is correct
15	Correct	99 ms	320 KB	Output is correct
16	Runtime error	1 ms	468 KB	Execution killed with signal 6
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	468 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	212 KB	Output is correct
2	Correct	94 ms	212 KB	Output is correct
3	Correct	101 ms	340 KB	Output is correct
4	Correct	102 ms	316 KB	Output is correct
5	Correct	95 ms	316 KB	Output is correct
6	Correct	90 ms	312 KB	Output is correct
7	Correct	92 ms	212 KB	Output is correct
8	Correct	95 ms	320 KB	Output is correct
9	Correct	95 ms	316 KB	Output is correct
10	Correct	95 ms	212 KB	Output is correct
11	Correct	93 ms	320 KB	Output is correct
12	Correct	90 ms	316 KB	Output is correct
13	Correct	96 ms	312 KB	Output is correct
14	Correct	93 ms	316 KB	Output is correct
15	Correct	99 ms	320 KB	Output is correct
16	Runtime error	1 ms	468 KB	Execution killed with signal 6
17	Halted	0 ms	0 KB	-