제출 #1282517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282517		duyanhchupapi	Team Contest (JOI22_team)	C++20	0 / 100	29 ms	5624 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];
int comp[N], nen[N], ind, bit[N], Minz[N], seg[4*N];
////// BIT
void update(int id, int vl) {
	while(id <= ind) bit[id] = max(bit[id], vl), id += -id&id;
}
int getmax(int id) {
	int res = -1;
	while(id > 0) res = max(res, bit[id]), id -= -id&id;
	return res;
}
////////// ST
void up(int x, int l, int r, int id, int w) {
	if(l == r) {
		seg[x] = max(seg[x], w + nen[id]);
		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] = max(seg[2*x+1], seg[2*x]);
}
int MAX(int x, int l, int r, int i, int j) {
	if(l > j || r < i) return -1;
	if(l >= i && r <= j) return seg[x];
	int m = (l+r)/2;
	return max(MAX(2*x,l,m,i,j), MAX(2*x+1,m+1,r,i,j));
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
	fill(bit, bit+N, -1);
	fill(seg, seg+4*N, -1);
	cin >> n;
	for(int i=1;i<=n;++i) cin >> p[i].x >> p[i].y >> p[i].z, comp[i] = p[i].y;
	
	sort(p+1,p+n+1, [&](const kid & p1, const kid & p2) {
		return p1.x < p2.x;
		return p1.y < p2.y;
		return p1.z < p2.z;
	});
	
	sort(comp+1,comp+n+1);
	for(int i=1;i<=n;++i) if(comp[i] != nen[ind]) nen[++ind] = comp[i];	
	for(int i=1;i<=n;++i) p[i].y = lower_bound(nen+1, nen+ind+1, p[i].y) - nen;
	
	//cout<<'\n';for(int i=1;i<=n;++i) cout<<p[i].x<<' '<<p[i].y<<' '<<p[i].z<<'\n';
	//cout<<'\n';
	int j = 1;
	for(int i=1;i<=n;i = j) {
		while(p[i].x == p[j].x) ++j;
		if(i != 1) {
			int idd = i;
			for(int id=i;id<j;id = idd) {
				while(p[id].y == p[idd].y && idd < j) ++idd;
				int Y = p[id].y, Z = p[id].z, ID = ind+1;
				int l = 1, r = ind;
				while(l <= r) {
					int mid = (l+r)/2;
					if(getmax(mid) > Z) ID = mid, r = mid - 1;
					else l = mid + 1;
				}
				
				ID = max(ID+1, Y+1);
				if(ID <= ind) ans = max(ans, p[i].x + MAX(1,1,ind,ID,ind));
			}
		}
		
		for(int id=i;id<j;++id) {
			int Y = p[id].y, Z = p[id].z;
			update(Y, Z);
			int val = getmax(Y - 1);
			if(val > Z) up(1, 1, ind, Y, val);
		}
	
	}
	
	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