Submission #733681

#	Time	Username	Problem	Language	Result	Execution time	Memory
733681		myrcella	Team Contest (JOI22_team)	C++17	100 / 100	721 ms	27908 KiB

team

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

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 2e5+10;
int n;
int x[maxn][3];
map <int,int> mp;
pii tree[2][maxn*4];
struct B{
	int a,b,c,id;
} beaver[maxn];

bool cmp1(B hi,B hii) {return hi.b<hii.b;}
bool cmp2(B hi,B hii) {return hi.a<hii.a;}

void update(int id,int c,int cl,int cr,int pos,pii val) {
	if (cl==cr) tree[id][c] = max(tree[id][c],val);
	else {
		int mid = cl+cr>>1;
		if (pos<=mid) update(id,c<<1,cl,mid,pos,val);
		else update(id,c<<1|1,mid+1,cr,pos,val);
		tree[id][c] = max(tree[id][c<<1],tree[id][c<<1|1]);
	}
}

pii query(int id,int c,int cl,int cr,int l,int r) {
	if (l<=cl and cr<=r) return tree[id][c];
	pii ret = {-1,-1};
	int mid=cl+cr>>1;
	if (l<=mid) ret = query(id,c<<1,cl,mid,l,r);
	if (r>mid) ret = max(ret,query(id,c<<1|1,mid+1,cr,l,r));
	return ret;
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	rep(i,0,n) rep(j,0,3) cin>>x[i][j];
	rep(j,0,3) {
		mp.clear();
		int tot = 0;
		rep(i,0,n) mp[x[i][j]] = 1;
		for (auto &it:mp) it.se = tot++;
		rep(i,0,n) {
			if (j==0) beaver[i].a = mp[x[i][j]];
			else if (j==1) beaver[i].b = mp[x[i][j]];
			else beaver[i].c = mp[x[i][j]];
		}
	}
	rep(i,0,n) beaver[i].id=i;
	//case 1: the beaver with highest Y has Z higher than the beaver with highest X
	sort(beaver,beaver+n,cmp1);
	int cur = 0;
	int ans = -1;
	rep(i,0,2) rep(j,0,maxn*4) tree[i][j] = {-1,-1};
	rep(i,0,n) {
		while (cur<n and beaver[cur].b<beaver[i].b) update(0,1,0,n-1,beaver[cur].a,{beaver[cur].c,beaver[cur].id}),update(1,1,0,n-1,beaver[cur].c,{beaver[cur].a,beaver[cur].id}),cur++;
		pii curx = query(1,1,0,n-1,0,beaver[i].c);
		if (curx.fi<=beaver[i].a) continue;
		pii curz = query(0,1,0,n-1,0,curx.fi-1);
		if (curz.fi<=beaver[i].c) continue;
		ans = max(ans,x[curx.se][0]+x[curz.se][2]+x[beaver[i].id][1]);
	}
	//case 2: the beaver with highest X has Z higher than the beaver with highest Y
	sort(beaver,beaver+n,cmp2);
	cur = 0;
	rep(i,0,2) rep(j,0,maxn*4) tree[i][j] = {-1,-1};
	rep(i,0,n) {
//		debug(beaver[i].id);
		while (cur<n and beaver[cur].a<beaver[i].a) update(0,1,0,n-1,beaver[cur].b,{beaver[cur].c,beaver[cur].id}),update(1,1,0,n-1,beaver[cur].c,{beaver[cur].b,beaver[cur].id}),cur++;
		pii cury = query(1,1,0,n-1,0,beaver[i].c);
		if (cury.fi<=beaver[i].b) continue;
		pii curz = query(0,1,0,n-1,0,cury.fi-1);
		if (curz.fi<=beaver[i].c) continue;
		ans = max(ans,x[cury.se][1]+x[curz.se][2]+x[beaver[i].id][0]);
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

team.cpp: In function 'void update(int, int, int, int, int, std::pair<int, int>)':
team.cpp:39:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   int mid = cl+cr>>1;
      |             ~~^~~
team.cpp: In function 'std::pair<int, int> query(int, int, int, int, int, int)':
team.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int mid=cl+cr>>1;
      |          ~~^~~

• 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