Submission #1282346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282346		c4l	Team Contest (JOI22_team)	C++20	0 / 100	925 ms	1114112 KiB

team

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct mem{
	int x, y, z;
};
mem a[150001];
vector<int> luu[600005];
vector<pair<int, int>> tr[600005];
int inf = (int)(-1e18);
struct pst{
	struct Node{
		int val;
		int l, r;
		Node(int v){
			val = v;
			l = -1, r= -1;
		}
	};
	vector<Node> luu;
	void clear(){
		luu.clear();
	}
	int build(int start, int end){
		if(start==end){
			Node tmp(inf);
			luu.push_back(tmp);
			return (int)luu.size()-1;
		}else{
			int mid = (start+end)/2;
			Node tmp(inf);
			int t = build(start, mid);
			int p = build(mid+1, end);
			tmp.l = t, tmp.r = p;
			luu.push_back(tmp);
			return (int)luu.size()-1;
		}
	}
	
	int update(int start, int end, int p, int x, int id){
		if(start==end){
			Node tmp(0);
			tmp.val = luu[id].val;
			tmp.val = max(tmp.val, x);
			luu.push_back(tmp);
			return (int)luu.size()-1;
		}else{
			int mid = (start+end)/2;
			Node tmp(0);
			tmp.val = luu[id].val;
			tmp.l = luu[id].l, tmp.r = luu[id].r;
			if(p<=mid){
				int tr = update(start, mid, p, x, luu[id].l);
				tmp.l = tr;
			}else{
				int tr = update(mid+1, end, p, x, luu[id].r);
				tmp.r = tr;
			}
			tmp.val = max(luu[tmp.l].val, luu[tmp.r].val);
			luu.push_back(tmp);
			return (int)luu.size()-1;
		}
	}
	
	int query(int start, int end, int l, int r, int id){
		if(start > r or end < l) return inf;
		if(l<=start and end<=r){
			return luu[id].val;
		}
		int mid = (start+end)/2;
		return max(query(start, mid, l, r, luu[id].l), query(mid+1,end, l, r, luu[id].r));
	}
};

pst cay[600005];
vector<int> seg[600005];
vector<int> pf[600005], lz[600005]; //X
void merge(vector<pair<int, int>> &A, vector<pair<int, int>> &B, vector<pair<int, int>> &C, int node){
	int i = 1, j = 1;
	int na = (int)A.size(), nb = (int)B.size();
	while(i<na && j<nb){
		if(A[i] < B[j]){
			C.push_back(A[i]);
			pf[node].push_back(pf[2*node][i]);
			i++;
		}else{
			C.push_back(B[j]);
			pf[node].push_back(pf[2*node+1][j]);
			j++;
		}
	}
	while(i<na){
		C.push_back(A[i]);
		pf[node].push_back(pf[2*node][i]);
		i++;
	}
	while(j<nb){
		C.push_back(B[j]);
		pf[node].push_back(pf[2*node+1][j]);
		j++;
	}
	
}

void merge2(vector<int> &A, vector<int> &B, vector<int> &C){
	int i = 1, j = 1;
	int na = (int)A.size(), nb = (int)B.size();
	while(i<na && j<nb){
		if(A[i] < B[j]){
			C.push_back(A[i]);
			i++;
		}else{
			C.push_back(B[j]);
			j++;
		}
	}
	while(i<na){
		C.push_back(A[i]);
		i++;
	}
	while(j<nb){
		C.push_back(B[j]);
		j++;
	}
	
}

void reset(int node, int start, int end){
	tr[node].clear();
	luu[node].clear();
	pf[node].clear();
	lz[node].clear();
	seg[node].clear();
	cay[node].clear();
	if(start!=end){
		int mid = (start+end)/2;
		reset(2*node, start, mid);
		reset(2*node+1, mid+1, end);
	}
}

void build(int node, int start, int end){
	tr[node].push_back({-1,-1});
	luu[node].push_back(-1);
	pf[node].push_back(-1);
	lz[node].push_back(-1);
	if(start==end){
		pf[node].push_back(a[start].x);
		tr[node].push_back({a[start].y, a[start].z});
		luu[node].push_back(a[start].z);
		lz[node].push_back(a[start].z);
		int m = (int)tr[node].size()-1;
		int root = cay[node].build(1, m);
		seg[node].push_back(root);
		for (int i = 1;i<=m;++i){
			int p = (int)(lower_bound(luu[node].begin()+1, luu[node].end(), tr[node][i].second) - luu[node].begin());
			// p should be in [1..m]
			if(p<1) p = 1;
			int nr = cay[node].update(1, m, p, pf[node][i], seg[node].back());
			seg[node].push_back(nr);
		}
	}else{
		int mid = (start+end)/2;
		build(2*node, start, mid);
		build(2*node+1, mid+1, end);
		merge(tr[2*node], tr[2*node+1], tr[node], node);
		merge2(luu[2*node], luu[2*node+1], luu[node]);
		int m= (int)tr[node].size()-1;
		int root = cay[node].build(1, m);
		seg[node].push_back(root);
		for (int i = 1;i<=m;++i){
			int p = (int)(lower_bound(luu[node].begin()+1, luu[node].end(), tr[node][i].second) - luu[node].begin());
			if(p<1) p = 1;
			int nr = cay[node].update(1, m, p, pf[node][i], seg[node].back());
			seg[node].push_back(nr);
		}
		for (int i = 1;i<=m;++i){
			lz[node].push_back(tr[node][i].second);
			lz[node][i] = max(lz[node][i], lz[node][i-1]);
		}
	}
}

int q1(int node, int start, int end, int l, int r, int y){
	if(start > r or end < l){
		return -1;
	}else if (l<=start and end<=r){
		// search among real elements (1..size-1)
		auto it = lower_bound(tr[node].begin()+1, tr[node].end(), make_pair((int)y, (int)-1));
		int p = (int)(it - tr[node].begin()) - 1; // p in [0..m]
		if(p < 0) p = 0;
		return lz[node][p];
	}else{
		int mid= (start+end)/2;
		return max(q1(2*node, start, mid, l, r, y), q1(2*node+1, mid+1, end, l, r, y));
	}
}

int q2(int node, int start, int end, int l, int r, int y, int z){
	if(start > r or end < l){
		return inf;
	}
	if(l<=start and end<=r){
		auto it = lower_bound(tr[node].begin()+1, tr[node].end(), make_pair((int)y, (int)-1));
		int p = (int)(it - tr[node].begin()) - 1; // p in [0..m]
		if(p < 0) p = 0;
		int m = (int)tr[node].size()-1;
		auto it2 = lower_bound(luu[node].begin()+1, luu[node].end(), z);
		int q = (int)(it2 - luu[node].begin()) - 1; // we want last index <= z
		if(q < 1) return inf; // nothing <= z
		int sol = cay[node].query(1, m, 1, q, seg[node][p]);
		return sol;
	}
	int mid = (start+end)/2;
	return max(q2(2*node, start, mid, l, r, y, z), q2(2*node+1, mid+1, end, l, r, y, z));
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	if(!(cin >> n)) return 0;
	for (int i = 1;i<=n;++i){
		cin >> a[i].x >> a[i].y >> a[i].z;
	}
	sort(a+1, a+n+1, [](mem p, mem q){
		return p.x < q.x;
	});
	int tro = 1;
	build(1, 1, n);
	int res = -1;
	for (int i = 2;i<=n;++i){
		while(tro<=n and a[tro].x<=a[i].x){
			tro++;
		}
		int mz = q1(1, 1, n, 1, i-1, a[i].y);
		if(mz != -1){
			int sol = q2(1, 1, n, tro, n, a[i].y, mz);
			if(sol!=inf){
				res = max(res, a[i].y + mz + sol);
			}
		}
	}
	reset(1, 1, n);
	for (int i = 1;i<=n;++i){
		swap(a[i].y, a[i].z);
	}
	tro = 1;
	build(1, 1, n);
	for (int i = 2;i<=n;++i){
		while(tro<=n and a[tro].x<=a[i].x){
			tro++;
		}
		int mz = q1(1, 1, n, 1, i-1, a[i].y);
		if(mz != -1){
			int sol = q2(1, 1, n, tro, n, a[i].y, mz);
			if(sol!=inf){
				res = max(res, a[i].y + mz + sol);
			}
		}
	}
	cout << res;
}

• 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