Submission #916449

#	Time	Username	Problem	Language	Result	Execution time	Memory
916449		GusterGoose27	Team Contest (JOI22_team)	C++17	100 / 100	148 ms	19960 KiB

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 j = 0; j < n;) {
		int p = j;
		int x = points[j][0];
		while (points[j][0] == x) {
			if (points[j][1] < bst[0][0] && points[j][2] < bst[1][1])
				best = max(best, (ll)points[j][0]+bst[0][0]+bst[1][1]);
			j++;
		}
		for (int i = p; i < j; i++) {
			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: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27