Submission #1282347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282347		duyanhchupapi	Team Contest (JOI22_team)	C++20	0 / 100	2094 ms	5320 KiB

team

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std; 
using ll = long long; 
const int N = 150005;
int n, inf = 1e9, ans = -1;

struct kid {
	int x,y,z;
} p[N];
vector <int> nen;
int seg[4*N], bit[N], luu[4*N];

void update(int id, int val) {
	while(id <= n) bit[id] = max(bit[id], val), id += -id&id;
}

int get(int id) {
	int res = -1;
	while(id > 0) res = max(res, bit[id]), id -= -id&id;
	return res;
}

void up(int x, int l, int r, int id, int w) {
	if(l == r) {
		int vl = nen[id] + w;
		if(seg[x] < vl || (seg[x] == vl && luu[x] < w))
			seg[x] = vl, luu[x] = w;
		return;
	}
	int m = (l + r)/2;
	if(id <= m) up(2*x,l,m,id,w);
	else up(2*x+1,m+1,r,id,w);
	seg[x] = seg[2*x];
	luu[x] = luu[2*x];
	if(seg[x] < seg[2*x+1] || (seg[x] == seg[2*x+1] && luu[x] < luu[2*x+1])) 
		seg[x] = seg[2*x+1], luu[x] = luu[2*x+1];
}

pair <int,int> MAX(int x, int l, int r, int i, int j) {
	if(l > j || r < i) return make_pair(-1,-1);
	if(l >= i && r <= j) return make_pair(seg[x], luu[x]);
	int m = (l + r)/2;
	pair <int,int> res = MAX(2*x,l,m,i,j);
	pair <int,int> RES = MAX(2*x+1,m+1,r,i,j);
	if(res.fi > RES.fi || (res.fi == RES.fi && res.se > RES.se)) return res;
	return RES;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
	cin >> n;
	fill(seg, seg+4*n+1, -1);
	for(int i=1;i<=n;++i) cin >> p[i].x >> p[i].y >> p[i].z, nen.push_back(p[i].y);
	sort(p+1,p+n+1, [&](const kid & p1, const kid & p2) {
		if(p1.x != p2.x) return p1.x < p2.x;
		else if(p1.y != p2.y) return p1.y < p2.y;
		return p1.z < p2.z;
	});
	//cout << '\n';
	//for(int i=1;i<=n;++i) cout << p[i].x << ' ' << p[i].y << ' ' << p[i].z << '\n'; cout << '\n';
	nen.push_back(0);
	sort(nen.begin(), nen.end());
	nen.erase(unique(nen.begin(), nen.end()), nen.end());
	for(int i=1;i<=n;++i) {
		p[i].y = lower_bound(nen.begin(), nen.end(), p[i].y) - nen.begin();
	}

	set <int> ms;
	int j = 1;
	for(int i=1;i<=n;++i) {
		while(p[i].x == p[j].x) ++j;
		if(!ms.empty()) {
			for(int id=i;id<j;++id) {
				int Y = p[id].y, Z = p[id].z;
				auto it = ms.upper_bound(Y);
				if(it == ms.end()) continue;
				int yi = *it;
 				pair <int,int> kq = {-1,-1};
 				if(yi <= n) kq = MAX(1,1,n,yi,n); 
 				if(kq.se > Z) ans = max(ans, p[i].x + kq.fi);
 				//cout << id << ' ' << yi << ' ' << kq.fi << ' ' << kq.se << '\n';
			}
		}
		
		for(int id=i;id<j;++id) {
			int Y = p[id].y, Z = p[id].z;
			update(Y, Z);
			int val = get(Y - 1);
			if(val > Z) up(1,1,n,Y,val);
			ms.insert(Y);	
		}
		// cout << ans << '\n';
	}
	
	cout << ans;
	return 0;
}

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