Submission #714013

#	Time	Username	Problem	Language	Result	Execution time	Memory
714013		089487	Team Contest (JOI22_team)	C++14	9 / 100	93 ms	13076 KiB

team

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
//#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define sz(x) (int)(x.size())
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
const int N=2e5+7;
const int INF=1e9;
int bit[N];
int bit2[N];
int x[N];
int y[N];
int z[N];
vector<pii> v[N];
int yz[N];
void upd(int x,int val){
	for(;x<N;x+=lowbit(x)) bit[x]=max(bit[x],val);
}
void upd2(int x,int val){
	for(;x>0;x-=lowbit(x)) bit2[x]=min(bit2[x],val);
}
int qry(int x){
	int ret=0;
	for(;x>0;x-=lowbit(x)) ret=max(ret,bit[x]);
	return ret;
}
int qry2(int x){
	int ret=INF;
	for(;x<N;x+=lowbit(x)) ret=min(ret,bit2[x]);
	return ret;
}
signed main(){
	quick
	int n;
	cin>>n;
	vector<int> vx;
	vector<int> vy;
	vector<int> vz;
	rep(i,0,n-1){
		cin>>x[i]>>y[i]>>z[i];
		vx.eb(x[i]);
		vy.eb(y[i]);
		vz.eb(z[i]);
	}	
	sort(all(vx));
	sort(all(vy));
	sort(all(vz));
	vx.erase(unique(all(vx)),vx.end());
	vy.erase(unique(all(vy)),vy.end());
	vz.erase(unique(all(vz)),vz.end());
	fill(bit2,bit2+N,INF);
	fill(bit,bit+N,0LL);
	int ans=-1;
	rep(i,0,n-1){
		x[i]=upper_bound(all(vx),x[i])-vx.begin();
		y[i]=upper_bound(all(vy),y[i])-vy.begin();
		z[i]=upper_bound(all(vz),z[i])-vz.begin();
		v[x[i]].eb(mp(y[i],z[i]));
		yz[y[i]]=INF;
	}
	
	rep(i,1,sz(vx)){
		for(pii p2:v[i]){
			int l=p2.F+1;
			int r=sz(vy);
			while(r-l>=5){
				int lx2=(l*2+r)/3;
				int rx2=(l+r*2)/3;
				if(qry(lx2-1)-qry2(lx2)>qry(rx2-1)-qry2(rx2)){
					r=rx2;
				}
				else l=lx2;
			}
			int mx=0;
			int mn=0;
			rep(x,l,r){
				if(qry(x-1)-qry2(x)>0) mx=max(mx,qry(x-1)),mn=x;
			}
			if(mx>p2.S){
				ans=max(ans,vx[i-1]+vy[mn-1]+vz[mx-1]);
			}
		}
		for(pii p2:v[i]){
			upd2(p2.F,p2.S);
			upd(p2.F,p2.S);
		}
	}
	cout<<ans<<"\n";

	return 0;
}

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