Submission #557979

#	Time	Username	Problem	Language	Result	Execution time	Memory
557979		DanShaders	Team Contest (JOI22_team)	C++17	100 / 100	445 ms	24548 KiB

team

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T, typename Comp = less<T>>
using ordered_set = x::tree<T, x::null_type, Comp, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 1.6e5;

using P = array<int, 3>;

P a[N];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> a[i][j];
		}
	}
	sort(a, a + n);
	ordered_set<pair<int, int>, greater<>> f, b;
	f.insert({a[0][1], a[0][2]}), b.insert({a[0][2], a[0][1]});
	ll ans = -1;
	int y = -1, z = -1;
	vector<tuple<int, int, int>> cands;
	for (int i = 1; i < n - 1; ++i) {
		// add a[i]
		auto [fit, sc1] = f.insert({a[i][1], a[i][2]});
		auto [bit, sc2] = b.insert({a[i][2], a[i][1]});
		if (sc1) {
			assert(sc2);
			{
				int j = int(f.order_of_key({a[i][1], a[i][2]}));
				auto other = *b.find_by_order(j);
				if (pair{a[i][2], a[i][1]} != other) {
					y = max({y, a[i][1], other.y});
					z = max({z, a[i][2], other.x});
				}
			}
			{
				int j = int(b.order_of_key({a[i][2], a[i][1]}));
				auto other = *f.find_by_order(j);
				if (pair{a[i][1], a[i][2]} != other) {
					y = max({y, a[i][1], other.x});
					z = max({z, a[i][2], other.y});
				}
			}
		}

		if (a[i][0] == a[i + 1][0]) {
			continue;
		}
		// [0; i] and [i + 1; n - 1]
		int x = -1;
		for (int j = i + 1; a[j][0] == a[i + 1][0]; ++j) {
			if (a[j][1] < y && a[j][2] < z) {
				x = a[j][0];
				break;
			}
		}
		if (x != -1) {
			ans = max(ans, 0ll + x + y + z);
		}
	}
	cout << ans;
}

• 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