Submission #972538

#	Time	Username	Problem	Language	Result	Execution time	Memory
972538		happy_node	Team Contest (JOI22_team)	C++17	100 / 100	778 ms	65716 KiB

team

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

typedef long long ll;

const int MX=2e5+5;
int N;
int X[MX],Y[MX],Z[MX],mn[MX];

vector<pair<int,int>> ops[MX];

priority_queue<int, vector<int>, greater<int>> pend[MX]; 

struct segtree {
    	pair<int,int> t[4 * MX];
 
     	void update(int v, int l, int r, int pos, int val) {
           	if(l > pos || r < pos) return;
           	if(l == r) {
                 	t[v] = make_pair(val, pos);
                 	return;
           	}
           	int mid = (l + r) >> 1;
           	update(v * 2 + 0, l, mid + 0, pos, val);
           	update(v * 2 + 1, mid + 1, r, pos, val);
           	t[v] = min(t[v * 2 + 0], t[v * 2 + 1]);
     	}
 
     	pair<int,int> query(int v, int l, int r, int ql, int qr) {
           	if(ql > r || qr < l) return make_pair(1e8, 1e8);
           	if(ql <= l && qr >= r) return t[v];
           	int mid = (l + r) >> 1;
           	return min(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
      	}

      	void prep() {
      		for(int i=0;i<4*MX;i++) t[i]=make_pair(1e8,i);
      	}
} st, tt;

priority_queue<pair<int,int>> pts;

int rx[MX], ry[MX], rz[MX];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	st.prep();
	tt.prep();

	cin>>N;

	map<int,int> ix,iy,iz;
	for(int i=0;i<N;i++) {
		cin>>X[i]>>Y[i]>>Z[i];
		ix[X[i]]=0;
		iy[Y[i]]=0;
		iz[Z[i]]=0;
	}

	int p=0;
	for(auto &[x,y]:ix) y=p++, rx[y]=x;
	p=0;
	for(auto &[x,y]:iy) y=p++, ry[y]=x;
	p=0;
	for(auto &[x,y]:iz) y=p++, rz[y]=x;

	for(int i=0;i<N;i++) {
		ops[iz[Z[i]]].push_back({ix[X[i]],iy[Y[i]]});
		pend[i].push(1e8);
		mn[i]=1e8;
	} 	

	int ans=-1;

	for(int z=0;z<N;z++) {
		// evaluate
		for(auto [x,y]:ops[z]) {
			if(pts.empty()) continue;
			auto [yy,xx]=pts.top();

			// wanna get rightmost x
			int l=xx+1,r=N,res=-1;
			while(l<=r) {
				int mid=(l+r)/2;
				if(tt.query(1,0,N,mid,N).first<yy) {
					res=mid,l=mid+1;
				} else {
					r=mid-1;
				}
			}

			if(res<=x||yy<=y) continue;

			ans=max(ans,rz[z]+ry[yy]+rx[res]);
		}	

		// insert
		for(auto [x,y]:ops[z]) {
			if(tt.query(1,0,N,x+1,N).first>=y) {
				pend[y].push(x);
				st.update(1,0,N,y,pend[y].top());
			} else {
				pts.push({y,x});
			}
			mn[x]=min(mn[x],y);
			tt.update(1,0,N,x,mn[x]);
		}

		for(auto [x,y]:ops[z]) {
			while(true) {
				auto [v,k]=st.query(1,0,N,y+1,N);
				if(v<x) {
					pts.push({k,v});
					pend[k].pop();
					st.update(1,0,N,k,pend[k].top());
				} else {
					break;
				}
			}
		}
	}

	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