oj.uz

Submission #596366

# Submission time Handle Problem Language Result Execution time Memory
596366 2022-07-14T15:59:06 Z flappybird Team Contest (JOI22_team) C++17
0 / 100
 38 ms 4540 KB 
#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 = 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.begin()) {
						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, 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 38 ms 4540 KB Output is correct
12 Incorrect 28 ms 3268 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 38 ms 4540 KB Output is correct
12 Incorrect 28 ms 3268 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 38 ms 4540 KB Output is correct
12 Incorrect 28 ms 3268 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 38 ms 4540 KB Output is correct
12 Incorrect 28 ms 3268 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -