Submission #596331

#	Time	Username	Problem	Language	Result	Execution time	Memory
596331		flappybird	Team Contest (JOI22_team)	C++17	0 / 100	1 ms	340 KiB

team

#include <bits/stdc++.h>
#define MAX 150101
#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];
int chk(pii p1, pii p2) {
	if (p1.first > p2.first && p1.second < p2.second) return 0;
	if (p1.first < p2.first && p1.second > p2.second) return 0;
	if (p1 == p2) return 2;
	if (p1 < p2) return 1;
	else return -1;
}
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 = 1; 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()) ans = max(ans, Z[i] + uxst.begin()->first + uyst.begin()->second);
		}
		isf = false;
		if (yst.empty()) {
			xst.emplace(X[0], Y[0]);
			yst.emplace(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.begin()) {
						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, 0))) {
				auto ity = yst.lower_bound(pii(x, 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