Submission #881782

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
881782	2023-12-01T22:23:32 Z	Hakiers	Team Contest (JOI22_team)	C++17	9 / 100	220 ms	5940 KB

team

#include <bits/stdc++.h>
using namespace std;
constexpr int BASE = 1 << 18;
struct cord{
	int x, y, z;
};
map<int, int> mapa[2];
int translate[2][BASE];
pair<int, int> TREE[2][BASE<<1];
cord INPUT[BASE];
int n;

bool cmp(cord a, cord b){
	
	if(a.z != b.z)
		return a.z < b.z;
	else if(a.x != b.x)
		return a.x < b.x;
		
	return a.y < b.y;
}

void scale(){
	int pos = 0;
	for(auto it = mapa[0].begin(); it != mapa[0].end(); ++it){
		it->second = ++pos;
		translate[0][pos] = it->first;
	}
		
	pos = 0;
	for(auto it = mapa[1].begin(); it != mapa[1].end(); ++it){
		it->second = ++pos;
		translate[1][pos] = it->first;
	}

	for(int i = 1; i <= n; i++){
		INPUT[i].x = mapa[0][INPUT[i].x];
		INPUT[i].y = mapa[1][INPUT[i].y];
	}
}

pair<int, int> merge(pair<int, int> a, pair<int, int> b){
	if(a.first != b.first)
		return max(a, b);
	else if(a.second < b.second)
		return a;
	
	return b;
}

void update(int v, int val, int t){
	v += BASE;
	TREE[t][v] = max(TREE[t][v], {val, v-BASE});
	v/=2;

	while(v > 0){
		int l = 2*v, r = 2*v+1;
		TREE[t][v] = merge(TREE[t][l], TREE[t][r]);
		v/=2;
	}
}

pair<int, int> query(int a, int b, int t){
	a += BASE - 1;
	b += BASE + 1;
	pair<int, int> res = {0, 0};
	
	while(a/2 != b/2){
		if(a%2 == 0) res = merge(res, TREE[t][a+1]);
		if(b%2 == 1) res = merge(res, TREE[t][b-1]);
		a/=2; b/=2;
	}

	return res;
}

bool check(int mid, cord a){
	pair<int, int> maxX = query(a.y, mid, 0);
	if(maxX.first <= a.x) return true;
	
	pair<int, int> maxY = query(a.x, maxX.first - 1, 1);
	if(maxY.first <= maxX.second) return false;
	
	return true;
}

int BS(cord a){
	int l = a.y +1, r = BASE - 1, mid;
	
	while(l < r){
		mid = (l +r)/2;
		if(check(mid, a)) l = mid+1;
		else r = mid;
	}
	
	if(!check(l, a)) l--;
	
	pair<int, int> maxX = query(a.y, l, 0);
	//cout << "maxX " << maxX.first << "\n";
	if(maxX.first <= a.x) return -1;
	pair<int, int> maxY = query(a.x, maxX.first - 1, 1);
	if(maxY.first <= maxX.second) return -1;
	//cout << "maxY " << maxY.first << "\n";
	return a.z + translate[0][maxX.first] + translate[1][maxY.first];
	//return 0;
}

int solve(){
	int res = -1;
	for(int i = 1; i <= n; i++){
		//cerr << "x " << INPUT[i].x << " y " << INPUT[i].y << " z " << INPUT[i].z << "\n";
		res = max(res, BS(INPUT[i]));
		update(INPUT[i].y, INPUT[i].x, 0);
		update(INPUT[i].x, INPUT[i].y, 1);
	}
	
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		cin >> INPUT[i].x >> INPUT[i].y >> INPUT[i].z;
		mapa[0][INPUT[i].x];
		mapa[1][INPUT[i].y];
	}
	scale();
	sort(INPUT + 1, INPUT + n + 1, cmp);
	cout << solve() << "\n";
}

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2396 KB	Output is correct
2	Correct	1 ms	2392 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2648 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	2 ms	2648 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	2 ms	2652 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Incorrect	1 ms	2396 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #2
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2396 KB	Output is correct
2	Correct	1 ms	2392 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2648 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	2 ms	2648 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	2 ms	2652 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Incorrect	1 ms	2396 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	2 ms	2508 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	188 ms	5696 KB	Output is correct
12	Correct	97 ms	5400 KB	Output is correct
13	Correct	151 ms	5544 KB	Output is correct
14	Correct	159 ms	5860 KB	Output is correct
15	Correct	158 ms	5696 KB	Output is correct
16	Correct	183 ms	5476 KB	Output is correct

Subtask #4
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	2 ms	2508 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	188 ms	5696 KB	Output is correct
12	Correct	97 ms	5400 KB	Output is correct
13	Correct	151 ms	5544 KB	Output is correct
14	Correct	159 ms	5860 KB	Output is correct
15	Correct	158 ms	5696 KB	Output is correct
16	Correct	183 ms	5476 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	0 ms	2396 KB	Output is correct
20	Correct	1 ms	2396 KB	Output is correct
21	Correct	4 ms	2652 KB	Output is correct
22	Correct	220 ms	5940 KB	Output is correct
23	Incorrect	150 ms	5656 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #5
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	2 ms	2508 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	188 ms	5696 KB	Output is correct
12	Correct	97 ms	5400 KB	Output is correct
13	Correct	151 ms	5544 KB	Output is correct
14	Correct	159 ms	5860 KB	Output is correct
15	Correct	158 ms	5696 KB	Output is correct
16	Correct	183 ms	5476 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	0 ms	2396 KB	Output is correct
20	Correct	1 ms	2396 KB	Output is correct
21	Correct	4 ms	2652 KB	Output is correct
22	Correct	220 ms	5940 KB	Output is correct
23	Incorrect	150 ms	5656 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	2 ms	2508 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	188 ms	5696 KB	Output is correct
12	Correct	97 ms	5400 KB	Output is correct
13	Correct	151 ms	5544 KB	Output is correct
14	Correct	159 ms	5860 KB	Output is correct
15	Correct	158 ms	5696 KB	Output is correct
16	Correct	183 ms	5476 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Correct	1 ms	2396 KB	Output is correct
19	Correct	0 ms	2396 KB	Output is correct
20	Correct	1 ms	2396 KB	Output is correct
21	Correct	4 ms	2652 KB	Output is correct
22	Correct	220 ms	5940 KB	Output is correct
23	Incorrect	150 ms	5656 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #7
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2396 KB	Output is correct
2	Correct	1 ms	2392 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2648 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	2 ms	2648 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	2 ms	2652 KB	Output is correct
17	Correct	1 ms	2396 KB	Output is correct
18	Incorrect	1 ms	2396 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Submission #881782

Compilation message

Subtask #1 0 / 8.0

Subtask #2 0 / 29.0

Subtask #3 9.0 / 9.0

Subtask #4 0 / 9.0

Subtask #5 0 / 9.0

Subtask #6 0 / 9.0

Subtask #7 0 / 27.0

Subtask #1
0 / 8.0

Subtask #2
0 / 29.0

Subtask #3
9.0 / 9.0

Subtask #4
0 / 9.0

Subtask #5
0 / 9.0

Subtask #6
0 / 9.0

Subtask #7
0 / 27.0