Submission #796686

#	Time	Username	Problem	Language	Result	Execution time	Memory
796686		MetalPower	Team Contest (JOI22_team)	C++17	100 / 100	321 ms	26516 KiB

team

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

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 150069;
const int INF = 1e9 + 7;

int N, arr[MX][3];
vector<int> cc[3];
vector<pii> ls[MX], cm;
set<pii> s;

struct segmax{
	int st[MX << 1];

	void build(){
		for(int i = 0; i < (MX << 1); i++) st[i] = -INF;
	}

	void upd(int p, int v){
		for(p += MX, st[p] = v, p >>= 1; p > 0; p >>= 1) st[p] = max(st[p << 1], st[p << 1|1]);
	}

	int que(int l, int r){
		int res = -INF;
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1) res = max(res, st[l++]);
			if(r & 1) res = max(res, st[--r]);
		}
		return res;
	}
} sx;

struct segmin{
	int st[MX << 1];

	void build(){
		for(int i = 0; i < (MX << 1); i++) st[i] = INF;
	}

	void upd(int p, int v){
		for(p += MX, st[p] = v, p >>= 1; p > 0; p >>= 1) st[p] = min(st[p << 1], st[p << 1|1]);
	}

	int que(int l, int r){
		int res = INF;
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1) res = min(res, st[l++]);
			if(r & 1) res = min(res, st[--r]);
		}
		return res;
	}
} sn;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < 3; j++){
			cin >> arr[i][j];
			cc[j].push_back(arr[i][j]);
		}
	}

	for(int j = 0; j < 3; j++){
		sort(cc[j].begin(), cc[j].end());
		cc[j].resize(unique(cc[j].begin(), cc[j].end()) - cc[j].begin());
	}

	for(int i = 0; i < N; i++){
		for(int j = 0; j < 3; j++) arr[i][j] = lower_bound(cc[j].begin(), cc[j].end(), arr[i][j]) - cc[j].begin();
		ls[arr[i][0]].push_back({arr[i][1], arr[i][2]});
		cm.push_back({arr[i][1], arr[i][2]});
	}

	sort(cm.begin(), cm.end());
	cm.resize(unique(cm.begin(), cm.end()) - cm.begin());

	int mx = -1, ans = -1;

	sx.build();
	sn.build();

	set<pii> s;

	for(int i = 0; i < N; i++){
		
		for(pii x : ls[i]){ // query

			if(mx == -1) continue;

			int lf = sx.que(0, mx);
			int l = mx + 1, r = N - 1, rg = -1;
			while(l <= r){
				int mid = l + r >> 1, curr = sn.que(mid, r);
				if(curr < lf) rg = mid, l = mid + 1;
				else r = mid - 1;
			}

			if(cm[rg].fi > x.fi && lf > x.se) ans = max(ans, cc[0][i] + cc[1][cm[rg].fi] + cc[2][lf]); 
		}

		for(pii x : ls[i]){ // update

			int idx = lower_bound(cm.begin(), cm.end(), x) - cm.begin();

			s.insert(x);
			set<pii>::iterator it = s.find(x);

			{
				it++;
				if(it != s.end() && x.se > (*it).se) mx = max(mx, idx);
				it--;
				if(it != s.begin()){
					it--;
					if((*it).se > x.se) mx = max(mx, (int) (lower_bound(cm.begin(), cm.end(), (*it)) - cm.begin()));
				}
			}

			sx.upd(idx, x.se);
			sn.upd(idx, x.se);
		}
	}

	cout << ans << '\n';
}

Compilation message (stderr)

team.cpp: In function 'int main()':
team.cpp:99:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     int mid = l + r >> 1, curr = sn.que(mid, r);
      |               ~~^~~

• 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