Submission #881972

#	Time	Username	Problem	Language	Result	Execution time	Memory
881972		Hakiers	Team Contest (JOI22_team)	C++17	100 / 100	474 ms	44880 KiB

team

#include <bits/stdc++.h>
using namespace std;
constexpr int BASE = 1 << 18;
struct cord{
	int x, y, z;
};
map<int, int> mapa[3];
int translate[3][BASE];
int TREE[2][BASE<<1];
pair<int, int> square;
vector<cord> sorted[BASE];
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;
	}
	
	pos = 0;
	for(auto it = mapa[2].begin(); it != mapa[2].end(); ++it){
		it->second = ++pos;
		translate[2][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];
		INPUT[i].z = mapa[2][INPUT[i].z];
	}
}



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

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

	return res;
}

int check(cord a){
	if(a.x >= square.first) return -1;
	if(a.y >= square.second) return -1;
	
	return translate[0][square.first] + translate[1][square.second] + translate[2][a.z];
}

void updatesquare(cord a){
	int maxX = query(0, a.y-1, 0);
	int maxY = query(0, a.x-1, 1);
	
	//jestem wtedy maxymalnym Y
	if(maxX > a.x)
		square = max(square, {maxX, a.y});
	
	//jestem wtedy maxymalnym X
	if(maxY > a.y)
		square = max(square, {a.x, maxY});
	
	update(a.y, a.x, 0);
	update(a.x, a.y, 1);
}

int solve(){
	int res = -1;
	for(int i = 1; i < BASE; i++){
		for(auto sor : sorted[i])
			res = max(res, check(sor));
		//cerr << "x " << INPUT[i].x << " y " << INPUT[i].y << " z " << INPUT[i].z << "\n";
		for(auto sor : sorted[i])
			updatesquare(sor);
	}
	
	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];
		mapa[2][INPUT[i].z];
	}
	scale();
	for(int i = 1; i <= n; i++)
		sorted[INPUT[i].z].push_back(INPUT[i]);
	
	cout << solve() << "\n";
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27