oj.uz

Submission #587784

# Submission time Handle Problem Language Result Execution time Memory
587784 2022-07-02T11:14:21 Z SeDunion Team Contest (JOI22_team) C++17
37 / 100
 48 ms 4716 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

#define y2 asljdklakjsdlkj
#define mp make_pair

using namespace std;
using ll = long long;

const int N = 2e5 + 123;
const ll inf = 1e18 + 213;

ll ans = -inf;

struct point {
	ll x, y, z;
};

point e[N];

bool cmp(point a, point b) {
	return a.x < b.x;
}

ll y1 = -inf, z1 = -inf, y2 = -inf, z2 = -inf;

set<pair<ll,ll>>ys,zs;

void make(ll y, ll z) {
	if (y < y1 && z > z2) {
		y2 = y, z2 = z;
	}
	if (y > y1 && z < z2) {
		y1 = y, z1 = z;
	}
}

void upd(ll y, ll z) {
	ys.insert(mp(y, z));
	zs.insert(mp(z, y));
	make(y, z);
	while (ys.size() && ys.begin()->first < y) {
		ll Y = ys.begin()->first, Z = ys.begin()->second;
		//cout << Y << " " << Z << " + " << y << " " << z << endl;
		if (Z > z && y1 == -inf) {
			y1 = y, z1 = z;
			y2 = Y, z2 = Z;
		}
		make(Y, Z);
		ys.erase(ys.begin());
	}
	while (zs.size() && zs.begin()->first < z) {
		ll Z = zs.begin()->first, Y = zs.begin()->second;
		//cout << Y << " " << Z << " + " << y << " " << z << endl;
		if (y < Y && y1 == -inf) {
			y1 = Y, z1 = Z;
			y2 = y, z2 = z;
		}
		make(Y, Z);
		zs.erase(zs.begin());
	}
}

void get(ll x, ll y, ll z) {
	//cout << x << " " << y << " " << z << " f\n";
	//cout << y1 << " " << z1 << " | " << y2 << " " << z2 << " s\n";
	if (y1 > y && y1 > y2 && z2 > z && z2 > z1) {
		ans = max(ans, x + y1 + z2);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0 ; i < n ; ++ i) {
		cin >> e[i].x >> e[i].y >> e[i].z;
	}
	sort(e, e + n, cmp);
	int j = 0;
	for (int i = 0 ; i < n ; ++ i) {
		while (j < i && e[j].x < e[i].x) {
			//cout << "add " << e[j].x << " " << e[j].y << " " << e[j].z << endl;
			upd(e[j].y, e[j].z);
			++j;
		}
		get(e[i].x, e[i].y, e[i].z);
	}
	cout << (ans > 0 ? ans : -1);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 324 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 212 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 324 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 3 ms 468 KB Output is correct
27 Correct 3 ms 436 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 3 ms 468 KB Output is correct
30 Correct 2 ms 340 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 2 ms 468 KB Output is correct
34 Correct 3 ms 468 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 2 ms 468 KB Output is correct
38 Correct 2 ms 468 KB Output is correct
39 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 232 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 328 KB Output is correct
11 Correct 48 ms 4716 KB Output is correct
12 Incorrect 31 ms 3248 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 232 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 328 KB Output is correct
11 Correct 48 ms 4716 KB Output is correct
12 Incorrect 31 ms 3248 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 232 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 328 KB Output is correct
11 Correct 48 ms 4716 KB Output is correct
12 Incorrect 31 ms 3248 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 232 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 328 KB Output is correct
11 Correct 48 ms 4716 KB Output is correct
12 Incorrect 31 ms 3248 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 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 324 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 3 ms 468 KB Output is correct
27 Correct 3 ms 436 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 3 ms 468 KB Output is correct
30 Correct 2 ms 340 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 2 ms 468 KB Output is correct
33 Correct 2 ms 468 KB Output is correct
34 Correct 3 ms 468 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 2 ms 468 KB Output is correct
38 Correct 2 ms 468 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 1 ms 324 KB Output is correct
44 Correct 1 ms 232 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 1 ms 212 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 0 ms 328 KB Output is correct
50 Correct 48 ms 4716 KB Output is correct
51 Incorrect 31 ms 3248 KB Output isn't correct
52 Halted 0 ms 0 KB -