Submission #567764

# Submission time Handle Problem Language Result Execution time Memory
567764 2022-05-24T07:22:00 Z maomao90 Team Contest (JOI22_team) C++17
0 / 100
31 ms 1996 KB
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template <class T>
bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;}
template <class T>
bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int) x.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;

#ifndef DEBUG
#define cerr if(0) cerr
#endif

const int MAXN = 150005;
const int INF = 1000000005;
const ll LINF = 1000000000000000005;

int n;
iii xyz[MAXN];
set<ii> st;
int ans;

int main() {
#ifndef DEBUG
	ios::sync_with_stdio(0), cin.tie(0);
#endif
	cin >> n;
	REP (i, 0, n) {
		int x, y, z; cin >> x >> y >> z;
		xyz[i] = {x, y, z};
	}
	sort(xyz, xyz + n, [&] (iii l, iii r) {
			return get<1>(l) < get<1>(r);
			});
	ans = -1;
	REP (i, 0, n) {
		auto [x, y, z] = xyz[i];
		if (st.size() >= 2) {
			int mx = prev(st.end()) -> FI, mz = st.begin() -> SE;
			int my = -INF;
			RREP (j, n - 1, i) {
				auto [cx, cy, cz] = xyz[j];
				if (cy == get<1>(xyz[i - 1])) break;
				if (cx < mx && cz < mz) {
					my = cy;
					break;
				}
			}
			if (my != -INF) {
				mxto(ans, mx + my + mz);
			}
		}
		auto [it, yes] = st.insert(ii{x, z});
		if (!yes) {
			continue;
		}
		if (next(it) != st.end() && next(it) -> SE >= z) {
			st.erase(it);
			continue;
		}
		while (it != st.begin() && prev(it) -> SE <= z) {
			st.erase(prev(it));
		}
		assert(next(it) == st.end() || it -> FI != next(it) -> FI);
		assert(it == st.begin() || it -> FI != prev(it) -> FI);
	}
	cout << ans << '\n';
	return 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 0 ms 212 KB Output is correct
5 Correct 1 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 0 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 0 ms 340 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -
# 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 0 ms 212 KB Output is correct
5 Correct 1 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 0 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 0 ms 340 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -
# 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 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 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 31 ms 1996 KB Output is correct
12 Incorrect 21 ms 1492 KB Output isn't correct
13 Halted 0 ms 0 KB -
# 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 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 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 31 ms 1996 KB Output is correct
12 Incorrect 21 ms 1492 KB Output isn't correct
13 Halted 0 ms 0 KB -
# 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 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 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 31 ms 1996 KB Output is correct
12 Incorrect 21 ms 1492 KB Output isn't correct
13 Halted 0 ms 0 KB -
# 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 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 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 31 ms 1996 KB Output is correct
12 Incorrect 21 ms 1492 KB Output isn't correct
13 Halted 0 ms 0 KB -
# 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 0 ms 212 KB Output is correct
5 Correct 1 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 0 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 0 ms 340 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -