Submission #547550

#	Time	Username	Problem	Language	Result	Execution time	Memory
547550		inksamurai	Team Contest (JOI22_team)	C++17	100 / 100	484 ms	34628 KiB

team

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
typedef long long ll;
using pii=pair<int,int>;
using vi=vec(int);
void print(){cout<<"\n";}
template<class H,class ...T>
void print(const H&v,const T...u){cout<<v<<' ',print(u...);}
// e

const int inf=1e11;
using tpii=pair<int,pii>;
#define all(a) a.begin(),a.end()

const int nax=800011;

int nseg;
int seg[nax];

void build(int n){
	nseg=1;
	while(nseg<=n){
		nseg*=2;
	}
}

void upd(int pos,int val,int v,int l,int r){
	int m=(l+r)/2;
	if(l==r-1){
		// cout<<v<<" "<<val<<"\n";
		seg[v]=val;
		return;
	}
	if(pos<m){
		upd(pos,val,v*2+1,l,m);
	}else{
		upd(pos,val,v*2+2,m,r);
	}
	seg[v]=max(seg[v*2+1],seg[v*2+2]);
}

void upd(int pos,int val){
	upd(pos,val,0,0,nseg);
}

int prod(int v,int l,int r,int _l,int _r){
	if(l>=_r or r<=_l){
		return -inf;
	}
	if(_l<=l and r<=_r){
		// cout<<"\n";
		// cout<<l<<" "<<r<<" "<<seg[v]<<"\n";
		return seg[v];
	}
	int m=(l+r)>>1;
	return max(prod(v*2+1,l,m,_l,_r),prod(v*2+2,m,r,_l,_r));
}

int prod(int l,int r){
	return prod(0,0,nseg,l,r);
}


signed main(){
	ios::sync_with_stdio(0),
	cin.tie(0);
	int n;
	cin>>n;

	vec(tpii) a(n);
	for(int i=0;i<n;i++){
		cin>>a[i].fi>>a[i].se.fi>>a[i].se.se;
	}

	vi zs;
	rep(i,n){
		zs.pb(a[i].fi);
	}
	sort(zs.begin(),zs.end());
	rep(i,n){
		a[i].fi=lower_bound(all(zs),a[i].fi)-zs.begin();
	}

	build(n);

	vec(vec(pii)) qols(sz(zs)+11);

	rep(t,2){
		sort(all(a),[&](tpii l,tpii r){
			return l.se.fi<r.se.fi;
		});
		vec(multiset<int>) rbts(sz(zs));
		rep(i,sz(zs)){
			upd(i,-inf);
		}
		for(int i=0;i<n;i++){
			rbts[a[i].fi].insert(a[i].se.se);
		}
		for(int i=0;i<sz(zs);i++){
			int val=(sz(rbts[i])?*prev(rbts[i].end()):-inf);
			// cout<<val<<" ";
			upd(i,val);
		}
		// cout<<prod(0,4)<<"\n";
		for(int i=n-1;i>=0;i--){
			vec(tpii) delay;
			{
				pii p=a[i].se;
				// cout<<a[i].fi<<" "<<a[i].se.fi<<" "<<a[i].se.se<<"\n";
				int z=a[i].fi;
				delay.pb({z,p});
				rbts[z].erase(rbts[z].find(p.se));
				int val=(sz(rbts[z])?*prev(rbts[z].end()):-inf);
				upd(z,val);
				while(i-1>=0 and a[i-1].se.fi==p.fi){
					pii np=a[i-1].se;
					int nz=a[i-1].fi;
					// upd(a[i-1].fi,-inf);
					rbts[nz].erase(rbts[nz].find(np.se));
					int val=(sz(rbts[nz])?*prev(rbts[nz].end()):-inf);
					upd(nz,val);
					delay.pb({a[i-1].fi,np});
					i-=1;
				}
			}
			// int val=prod(0,a[i].fi);
			// // return maxY in Zs an Xs smaller than me
			for(auto tp:delay){
				int z=tp.fi;
				int x=tp.se.fi;
				int y=tp.se.se;

				int val=prod(0,z+1);
				
				// cout<<z<<" "<<x<<" "<<y<<"\n";
				// cout<<val<<"\n";

				if(val>y){
					// cout<<"ho\n";
					if(!t){
						qols[z+1].pb({x,val});
					}
					else{
						qols[z+1].pb({val,x});
					}
					// + 1 because p.se can't use this
				}
			}
		}
		rep(i,n){
			swap(a[i].se.se,a[i].se.fi);
		}
	}
	
	vec(pii) rbe(sz(zs)+11);
	pii fip={-inf,-inf};

	for(int i=0;i<sz(zs);i++){
		// cout<<zs[i]<<"\n";
		for(auto p:qols[i]){
			// cout<<p.fi<<" "<<p.se<<"\n";
			if(p.fi>fip.fi){
				fip=p;
			}else if(p.fi==fip.fi and p.se>fip.se){
				fip=p;
			}
		}
		rbe[i]=fip;		
	}

	int ans=-1;
	for(int i=0;i<n;i++){
		pii p=a[i].se;
		int z=a[i].fi;
		if(rbe[z].fi>p.fi and rbe[z].se>p.se){
			ans=max(ans,zs[a[i].fi]+rbe[z].fi+rbe[z].se);
		}
	}
	print(ans);
//	
	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