Submission #881782

#	Time	Username	Problem	Language	Result	Execution time	Memory
881782		Hakiers	Team Contest (JOI22_team)	C++17	9 / 100	220 ms	5940 KiB

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
• Subtask 2: 0 / 29
• Subtask 3: 9 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27