Submission #544545

#	Time	Username	Problem	Language	Result	Execution time	Memory
544545		benson1029	Team Contest (JOI22_team)	C++14	100 / 100	700 ms	17988 KiB

team

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> v[150005];
vector< pair<int,int> > a[3];
int seg1[600005], seg2[600005];
int mp[3][150005];

void seg1_upd(int x, int l, int r, int ll, int rr, int val) {
	if(ll <= l && r <= rr) {
		seg1[x] = max(seg1[x], val);
	} else if(ll > r || rr < l) {
		return;
	} else {
		seg1_upd(x*2, l, (l+r)/2, ll, rr, val);
		seg1_upd(x*2+1, (l+r)/2+1, r, ll, rr, val);
	}
}

void seg2_upd(int x, int l, int r, int ll, int rr, int val) {
	if(seg2[x] == 0) seg2[x] = 1e9;
	if(ll <= l && r <= rr) {
		seg2[x] = min(seg2[x], val);
	} else if(ll > r || rr < l) {
		return;
	} else {
		seg2_upd(x*2, l, (l+r)/2, ll, rr, val);
		seg2_upd(x*2+1, (l+r)/2+1, r, ll, rr, val);
	}
}

int seg1_qry(int x, int l, int r, int pos) {
	int tmp = seg1[x];
	if(l != r) {
		if(pos <= (l+r)/2) tmp = max(tmp, seg1_qry(x*2, l, (l+r)/2, pos));
		else tmp = max(tmp, seg1_qry(x*2+1, (l+r)/2+1, r, pos));
	}
	return tmp;
}

int seg2_qry(int x, int l, int r, int pos) {
	if(seg2[x] == 0) seg2[x] = 1e9;
	int tmp = seg2[x];
	if(l != r) {
		if(pos <= (l+r)/2) tmp = min(tmp, seg2_qry(x*2, l, (l+r)/2, pos));
		else tmp = min(tmp, seg2_qry(x*2+1, (l+r)/2+1, r, pos));
	}
	return tmp;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0; i<n; i++) {
		v[i].resize(3);
		cin >> v[i][0] >> v[i][1] >> v[i][2];
		a[0].push_back({v[i][0], i});
		a[1].push_back({v[i][1], i});
		a[2].push_back({v[i][2], i});
	}
	sort(a[0].begin(), a[0].end());
	sort(a[1].begin(), a[1].end());
	sort(a[2].begin(), a[2].end());
	for(int i=0; i<3; i++) {
		int tmp = 0;
		for(int j=0; j<n; j++) {
			if(j==0 || a[i][j].first!=a[i][j-1].first) tmp++;
			mp[i][tmp] = a[i][j].first;
			v[a[i][j].second][i] = tmp;
		}
	}
	sort(v, v+n);
	
	int ans = -1;
	int pos = 0; 
	
	for(int i=0; i<n; i++) {
		
		if(pos>0) {
			if(pos > v[i][1] && seg1_qry(1, 1, n, pos) > v[i][2]) {
				//cout << seg1_qry(1, 1, n, l) << " " << seg2_qry(1, 1, n, l) << "\n";
				ans = max(ans, mp[2][seg1_qry(1, 1, n, pos)] + mp[1][pos] + mp[0][v[i][0]]);
			}
		}
		
		if(i<n-1 && v[i][0] != v[i+1][0]) {
			for(int j=i; (j>=0 && v[j][0]==v[i][0]); j--) {
				seg2_upd(1, 1, n, 1, v[j][1], v[j][2]);
				seg1_upd(1, 1, n, v[j][1]+1, n, v[j][2]);
				
				int l,r,mid;
				l = v[j][1]+1; r = n;
				while(l<r) {
					mid = (l+r+1)/2;
					if(seg1_qry(1, 1, n, mid) > v[j][2]) r = mid - 1;
					else l = mid;
				}
				
				if(l<=n && seg1_qry(1, 1, n, l) == v[j][2]) {
					r = l; l = v[j][1] + 1;
					while(l<r) {
						mid = (l+r+1)/2;
						if(seg2_qry(1, 1, n, mid) >= v[j][2]) r = mid - 1;
						else l = mid;
					}
					if(seg2_qry(1, 1, n, l) < v[j][2]) {
						pos = max(pos, l);
					}
				}
				
				if(seg1_qry(1, 1, n, v[j][1]) > seg2_qry(1, 1, n, v[j][1])) {
					pos = max(pos, v[j][1]);
				}
			}
		}
		
	}
	cout << ans << "\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