답안 #733005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
733005	2023-04-30T02:06:08 Z	SanguineChameleon	Boat (APIO16_boat)	C++17	9 / 100	130 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 begin_t = (i == 1 || events[i].first != events[i - 1].first);
		bool end_t = (i == n * 2 || events[i].first != events[i + 1].first);
		if (begin_t) {
			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_t && 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

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	316 KB	Output is correct
2	Correct	101 ms	212 KB	Output is correct
3	Correct	130 ms	312 KB	Output is correct
4	Correct	113 ms	312 KB	Output is correct
5	Correct	95 ms	312 KB	Output is correct
6	Correct	108 ms	320 KB	Output is correct
7	Correct	97 ms	312 KB	Output is correct
8	Correct	96 ms	316 KB	Output is correct
9	Correct	94 ms	316 KB	Output is correct
10	Correct	102 ms	212 KB	Output is correct
11	Correct	118 ms	316 KB	Output is correct
12	Correct	94 ms	316 KB	Output is correct
13	Correct	103 ms	328 KB	Output is correct
14	Correct	97 ms	312 KB	Output is correct
15	Correct	94 ms	320 KB	Output is correct
16	Correct	19 ms	336 KB	Output is correct
17	Correct	21 ms	340 KB	Output is correct
18	Correct	20 ms	348 KB	Output is correct
19	Correct	20 ms	348 KB	Output is correct
20	Correct	20 ms	332 KB	Output is correct

Subtask #2

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	316 KB	Output is correct
2	Correct	101 ms	212 KB	Output is correct
3	Correct	130 ms	312 KB	Output is correct
4	Correct	113 ms	312 KB	Output is correct
5	Correct	95 ms	312 KB	Output is correct
6	Correct	108 ms	320 KB	Output is correct
7	Correct	97 ms	312 KB	Output is correct
8	Correct	96 ms	316 KB	Output is correct
9	Correct	94 ms	316 KB	Output is correct
10	Correct	102 ms	212 KB	Output is correct
11	Correct	118 ms	316 KB	Output is correct
12	Correct	94 ms	316 KB	Output is correct
13	Correct	103 ms	328 KB	Output is correct
14	Correct	97 ms	312 KB	Output is correct
15	Correct	94 ms	320 KB	Output is correct
16	Correct	19 ms	336 KB	Output is correct
17	Correct	21 ms	340 KB	Output is correct
18	Correct	20 ms	348 KB	Output is correct
19	Correct	20 ms	348 KB	Output is correct
20	Correct	20 ms	332 KB	Output is correct
21	Runtime error	1 ms	468 KB	Execution killed with signal 6
22	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	316 KB	Output is correct
2	Correct	101 ms	212 KB	Output is correct
3	Correct	130 ms	312 KB	Output is correct
4	Correct	113 ms	312 KB	Output is correct
5	Correct	95 ms	312 KB	Output is correct
6	Correct	108 ms	320 KB	Output is correct
7	Correct	97 ms	312 KB	Output is correct
8	Correct	96 ms	316 KB	Output is correct
9	Correct	94 ms	316 KB	Output is correct
10	Correct	102 ms	212 KB	Output is correct
11	Correct	118 ms	316 KB	Output is correct
12	Correct	94 ms	316 KB	Output is correct
13	Correct	103 ms	328 KB	Output is correct
14	Correct	97 ms	312 KB	Output is correct
15	Correct	94 ms	320 KB	Output is correct
16	Correct	19 ms	336 KB	Output is correct
17	Correct	21 ms	340 KB	Output is correct
18	Correct	20 ms	348 KB	Output is correct
19	Correct	20 ms	348 KB	Output is correct
20	Correct	20 ms	332 KB	Output is correct
21	Runtime error	1 ms	468 KB	Execution killed with signal 6
22	Halted	0 ms	0 KB	-