Submission #551948

#	Time	Username	Problem	Language	Result	Execution time	Memory
551948		QwertyPi	Team Contest (JOI22_team)	C++14	100 / 100	171 ms	22008 KiB

team

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int N = 1.5e5 + 5;
const int inf = 3e8 + 13;
int n, L;

struct tp{
	int a, b, c;
	bool operator< (const tp& o) const{
		return a < o.a || a == o.a && b < o.b || a == o.a && b == o.b && c < o.c;
	}
};

tp A[N];
int mx[3][N];
vector<tp> teams;

int ans = -1;

set<pii> S;
int cur_b = -inf, cur_c = -inf;
void add(int b, int c){
	// cout << "add " << b << ' ' << c << endl;
	auto ptr = S.lower_bound({b, c});
	// for(auto i : S) cout << i.fi << ' ' << i.se << '*'; cout << endl;
	if(ptr != S.end() && (ptr->fi > b && ptr->se < c || ptr->fi < b && ptr->se > c)){
		pii pa = *ptr;
		// cout << pa.fi << ' ' << pa.se << endl;
		// for(auto i : S) cout << i.fi << ' ' << i.se << '*'; cout << endl;
		while(*S.begin() != pa) S.erase(S.begin());
		// for(auto i : S) cout << i.fi << ' ' << i.se << '*'; cout << endl;
		while(S.begin() != S.end()){
			auto ptr = S.begin();
			if(!(ptr->fi > b && ptr->se < c || ptr->fi < b && ptr->se > c)){
				break;
			}
			S.erase(S.begin());
			cur_b = max(cur_b, max(ptr->fi, b));
			cur_c = max(cur_c, max(ptr->se, c));
		}
	}else if(ptr != S.begin() && (prev(ptr)->fi > b && prev(ptr)->se < c || prev(ptr)->fi < b && prev(ptr)->se > c)){
		pii pa = *prev(ptr);
		// cout << pa.fi << ' ' << pa.se << endl;
		// for(auto i : S) cout << i.fi << ' ' << i.se << '*'; cout << endl;
		while(*S.begin() != pa) S.erase(S.begin());
		// for(auto i : S) cout << i.fi << ' ' << i.se << '*'; cout << endl;
		while(S.begin() != S.end()){
			auto ptr = S.begin();
			if(!(ptr->fi > b && ptr->se < c || ptr->fi < b && ptr->se > c)){
				break;
			}
			S.erase(S.begin());
			cur_b = max(cur_b, max(ptr->fi, b));
			cur_c = max(cur_c, max(ptr->se, c));
		}
	}else{
		if(b >= cur_b && c >= cur_c){
			S.insert({b, c});
		}else if((b < cur_b && c > cur_c) || (b > cur_b && c < cur_c)){
			cur_b = max(b, cur_b), cur_c = max(c, cur_c);
		}
	}
}

int qry(int b, int c){
	// cout << "qry " << b << ' ' << c << ' ' << cur_b << ' ' << cur_c << endl;
	if(cur_b <= b || cur_c <= c) return -inf;
	return cur_b + cur_c;
}

void check(int i, int j, int k){
	if(A[i].a > A[j].a && A[i].a > A[k].a && A[j].b > A[i].b && A[j].b > A[k].b && A[k].c > A[i].c && A[k].c > A[j].c)
		ans = max(ans, A[i].a + A[j].b + A[k].c);
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	set<tp> S;
	for(int i = 0; i < n; i++){
		int a, b, c;
		cin >> a >> b >> c;
		S.insert({a, b, c});
	}
	n = 0;
	for(auto i : S){
		A[n++] = i;
	}
//	cout << n << endl;
//	for(int i = 0; i < n; i++){
//		cout << A[i].a << ' ' << A[i].b << ' ' << A[i].c << endl;
//	}
	S.insert({inf, inf});
	int l = 0, r = -1;
	while(l < n){
		while(r + 1 < n && A[r + 1].a == A[l].a) r++;
		for(int i = l; i <= r; i++){
			ans = max(ans, A[i].a + qry(A[i].b, A[i].c));
		}
		for(int i = l; i <= r; i++){
			add(A[i].b, A[i].c);
		}
		l = r + 1;
	}
	cout << ans << endl;
}

Compilation message (stderr)

team.cpp: In member function 'bool tp::operator<(const tp&) const':
team.cpp:15:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   15 |   return a < o.a || a == o.a && b < o.b || a == o.a && b == o.b && c < o.c;
      |                     ~~~~~~~~~^~~~~~~~~~
team.cpp:15:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   15 |   return a < o.a || a == o.a && b < o.b || a == o.a && b == o.b && c < o.c;
      |                                            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
team.cpp: In function 'void add(int, int)':
team.cpp:31:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   31 |  if(ptr != S.end() && (ptr->fi > b && ptr->se < c || ptr->fi < b && ptr->se > c)){
      |                        ~~~~~~~~~~~~^~~~~~~~~~~~~~
team.cpp:39:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   39 |    if(!(ptr->fi > b && ptr->se < c || ptr->fi < b && ptr->se > c)){
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~
team.cpp:46:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   46 |  }else if(ptr != S.begin() && (prev(ptr)->fi > b && prev(ptr)->se < c || prev(ptr)->fi < b && prev(ptr)->se > c)){
      |                                ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
team.cpp:54:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   54 |    if(!(ptr->fi > b && ptr->se < c || ptr->fi < b && ptr->se > c)){
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~

• 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