제출 #714024

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
714024		089487	Team Contest (JOI22_team)	C++14	100 / 100	195 ms	15232 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 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);
}
int qry(int x){
	int ret=0;
	for(;x>0;x-=lowbit(x)) ret=max(ret,bit[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());
	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;
	}
	int Best=-1;
	rep(i,1,sz(vx)){
		for(pii p2:v[i]){
			if(Best>p2.F&&qry(Best-1)>p2.S){
				ans=max(ans,vx[i-1]+vy[Best-1]+vz[qry(Best-1)-1]);
			}
		}
		for(pii p2:v[i]){
			yz[p2.F]=min(yz[p2.F],p2.S);
			if(qry(p2.F-1)>yz[p2.F]){
				Best=max(Best,p2.F);
			}
			upd(p2.F,p2.S);
		}
	}
	cout<<ans<<"\n";
 
	return 0;
}

• 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