Submission #916448

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
916448	2024-01-26T00:25:10 Z	GusterGoose27	Team Contest (JOI22_team)	C++17	0 / 100	37 ms	2140 KB

team

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 15e4+5;
const int inf = 2e9;
typedef long long ll;
typedef array<int, 2> arr2;
typedef array<int, 3> arr3;

arr3 points[MAXN];
int n;

const arr2 def({-1, -1});

arr2 get_prev(set<arr2> &vals, arr2 cur) {
	auto v = vals.upper_bound(cur);
	if (v == vals.begin()) return def;
	return *(--v);
}

bool dom(arr2 a, arr2 b) {
	return a[0] >= b[0] && a[1] >= b[1];
}

arr2 rev(arr2 a) {
	return arr2({a[1], a[0]});
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) cin >> points[i][j];
	}
	sort(points, points+n);
	set<arr2> tail({{inf, inf}});
	set<arr2> tail_rev({{inf, inf}});
	arr2 bst[2] = {def, def};
	ll best = -1;
	for (int i = 0; i < n; i++) {
		if (points[i][1] < bst[0][0] && points[i][2] < bst[1][1])
			best = max(best, (ll)points[i][0]+bst[0][0]+bst[1][1]);
		arr2 cur({points[i][1], points[i][2]});
		if (tail.find(cur) != tail.end()) continue;
		
		// case 1: add to tail

		arr2 prv = get_prev(tail, cur);
		arr2 nxt = *(tail.upper_bound(cur));
		if (((prv != def && dom(cur, prv)) ||
				(prv == def && dom(cur, bst[0]) && dom(cur, bst[1])))
				&& dom(nxt, cur)) { // added to tail
			tail.insert(cur);
			tail_rev.insert(rev(cur));
			continue;
		}
		
		// case 2: ignorable

		if (cur[0] <= bst[0][0] && cur[1] <= bst[0][1]) {
			continue;
		}

		// case 3: special insert

		arr2 s = *tail.begin();
		if (dom(s, cur)) {
			if (cur[0] > bst[0][0]) {
				bst[0] = cur;
			}
			else if (cur[1] > bst[1][1]) {
				bst[1] = cur;
			}
			continue;
		}

		// case 4: lower insert

		if (cur[1] < prv[1]) {
			arr2 popped;
			do {
				popped = *tail.begin();
				tail.erase(popped);
				tail_rev.erase(rev(popped));
			} while (popped != prv);
			bst[0] = cur;
			bst[1] = prv;
			continue;
		}

		prv = rev(get_prev(tail_rev, rev(cur)));
		nxt = rev(*tail_rev.upper_bound(rev(cur)));

		assert(cur[0] < prv[0]);
		arr2 popped;
		do {
			popped = *tail.begin();
			tail.erase(popped);
			tail_rev.erase(rev(popped));
		} while (popped != prv);
		bst[0] = prv;
		bst[1] = cur;
	}
	cout << best << '\n';
}

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Incorrect	0 ms	348 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #2
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Incorrect	0 ms	348 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	356 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	37 ms	2140 KB	Output is correct
12	Incorrect	21 ms	1628 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	356 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	37 ms	2140 KB	Output is correct
12	Incorrect	21 ms	1628 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	356 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	37 ms	2140 KB	Output is correct
12	Incorrect	21 ms	1628 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	356 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	37 ms	2140 KB	Output is correct
12	Incorrect	21 ms	1628 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #7
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Incorrect	0 ms	348 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Submission #916448

Compilation message

Subtask #1 0 / 8.0

Subtask #2 0 / 29.0

Subtask #3 0 / 9.0

Subtask #4 0 / 9.0

Subtask #5 0 / 9.0

Subtask #6 0 / 9.0

Subtask #7 0 / 27.0

Subtask #1
0 / 8.0

Subtask #2
0 / 29.0

Subtask #3
0 / 9.0

Subtask #4
0 / 9.0

Subtask #5
0 / 9.0

Subtask #6
0 / 9.0

Subtask #7
0 / 27.0