Submission #1206846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206846		AmirAli_H1	Team Contest (JOI22_team)	C++20	100 / 100	120 ms	7608 KiB

team

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 19) + 4;
const int oo = 1e9 + 4;

int n;
pair<int, pii> A[maxn];
vector<int> arr; set<pii> st;
int tx[2][maxn];

int GI(int x) {
	return lower_bound(all(arr), x) - arr.begin();
}

void set_mx(int I, int i, int x) {
	for (++i; i < maxn; i += (i & -i)) tx[I][i] = max(tx[I][i], x);
}

int get_mx(int I, int i) {
	int res = 0;
	for (++i; i > 0; i -= (i & -i)) res = max(res, tx[I][i]);
	return res;
}

void addp(int A1, int A2) {
	auto it = st.lower_bound(Mp(A1, -1));
	if (it != st.end()) {
		auto f = *it;
		if (f.F >= A1 && f.S >= A2) return ;
	}
	it = st.upper_bound(Mp(A1, oo));
	while (true) {
		if (it == st.begin()) break;
		it--; auto f = *it;
		if (f.S <= A2) st.erase(f);
		else break;
		it = st.upper_bound(Mp(A1, oo));
	}
	st.insert(Mp(A1, A2));
}

void addx(int i) {
	int j1 = GI(A[i].S.F), j2 = GI(A[i].S.S);
	int valx = get_mx(0, j1 - 1); set_mx(0, j1, A[i].S.S);
	if (valx > A[i].S.S) addp(A[i].S.F, valx);
	valx = get_mx(1, j2 - 1); set_mx(1, j2, A[i].S.F);
	if (valx > A[i].S.F) addp(valx, A[i].S.S);
}

void solve() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> A[i].F >> A[i].S.F >> A[i].S.S;
		arr.pb(A[i].F); arr.pb(A[i].S.F); arr.pb(A[i].S.S);
	}
	sort(A, A + n); sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());

	int ans = 0, j = 0;
	for (int i = 0; i < n; i++) {
		if (A[i].F != A[j].F) {
			for (int R = j; R < i; R++) addx(R);
			j = i;
		}
		for (auto f : st) {
			if (f.F > A[i].S.F && f.S > A[i].S.S) ans = max(ans, A[i].F + f.F + f.S);
		}
	}
	if (ans == 0) cout << -1 << endl;
	else cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int T = 1;
	while (T--) {
		solve();
	}
	
	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