Submission #596381

#	Time	Username	Problem	Language	Result	Execution time	Memory
596381		flappybird	Team Contest (JOI22_team)	C++17	0 / 100	38 ms	4652 KiB

team

#include <bits/stdc++.h>
#define MAX 150101
#define INF 100000001
#define ln '\n'
using namespace std;
vector<tuple<int, int, int>> in;
typedef pair<int, int> pii;
int X[MAX];
int Y[MAX];
int Z[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N;
	cin >> N;
	int i;
	int a, b, c;
	for (i = 1; i <= N; i++) cin >> a >> b >> c, in.push_back({ c, a, b });
	sort(in.begin(), in.end());
	for (i = 0; i < N; i++) tie(Z[i], X[i], Y[i]) = in[i];
	set<pii> xst, yst;
	set<pii> uxst, uyst; //unique
	int ans = -1;
	map<pii, int> mp;
	map<int, vector<int>> vmp;
	for (i = 0; i < N; i++) vmp[Z[i]].push_back(i);
	bool isf = true;
	for (auto it = vmp.begin(); it != vmp.end(); it++) {
		if (!isf) {
			for (auto i : it->second) if (uxst.size() && uyst.size() && uxst.rbegin()->first > X[i] && uyst.rbegin()->second > Y[i]) ans = max(ans, Z[i] + uxst.rbegin()->first + uyst.rbegin()->second);
		}
		isf = false;
		if (yst.empty()) {
			xst.emplace(X[0], Y[0]);
			yst.emplace(X[0], Y[0]);
			mp[pii(X[0], Y[0])]++;
			mp[pii(X[0], Y[0])]++;
		}
		for (auto i : it->second) {
			if (!i) continue;
			int x, y;
			x = X[i];
			y = Y[i];
			if (!xst.count(pii(x, y))) {
				auto itx = xst.lower_bound(pii(x, 0));
				if (itx == xst.end() || itx->second > y) {
					if (itx == xst.end()) itx--;
					vector<pii> er;
					while (1) {
						if (itx->second >= y) er.push_back(*itx);
						else break;
						if (itx == xst.begin()) break;
						itx--;
					}
					for (auto& v : er) {
						int res = --mp[v];
						if (res == 1) uyst.insert(v);
						if (res == 0) uxst.erase(v);
						xst.erase(v);
					}
					int res = ++mp[pii(x, y)];
					if (res == 1) uxst.insert(pii(x, y));
					if (res == 2) uxst.erase(pii(x, y)), uyst.erase(pii(x, y));
					xst.insert(pii(x, y));
				}
			}
			if (!yst.count(pii(x, y))) {
				auto ity = yst.lower_bound(pii(x + 1, 0));
				if (ity == yst.begin() || prev(ity)->second < y) {
					vector<pii> er;
					while (ity != yst.end()) {
						if (ity->second <= y) er.push_back(*ity);
						else break;
						ity++;
					}
					for (auto& v : er) {
						int res = --mp[v];
						if (res == 1) uxst.insert(v);
						if (res == 0) uyst.erase(v);
						yst.erase(v);
					}
					int res = ++mp[pii(x, y)];
					if (res == 1) uyst.insert(pii(x, y));
					if (res == 2) uxst.erase(pii(x, y)), uyst.erase(pii(x, y));
					yst.insert(pii(x, y));
				}
			}
		}
	}
	cout << ans << ln;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27