Submission #1206877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206877		AmirAli_H1	Team Contest (JOI22_team)	C++20	100 / 100	156 ms	19916 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;

struct node {
	int res, max, min;
};

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

node f(node a, node b) {
	node res;
	res.res = max(a.res, b.res);
	res.max = max(a.max, b.max);
	res.min = min(a.min, b.min);
	return res;
}

void build(int v, int tl, int tr) {
	if (tr - tl == 1) {
		t[v] = null;
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

void set_val(int v, int tl, int tr, int i, int x) {
	if (i >= tr || i < tl) return ;
	if (tr - tl == 1) {
		t[v].res = arr[tl] + x;
		t[v].max = x; t[v].min = x;
		return ;
	}
	int mid = (tl + tr) / 2;
	if (i < mid) set_val(2 * v + 1, tl, mid, i, x);
	else set_val(2 * v + 2, mid, tr, i, x);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

void del_val(int v, int tl, int tr, int i) {
	if (i >= tr || i < tl) return ;
	if (tr - tl == 1) {
		t[v] = null;
		return ;
	}
	int mid = (tl + tr) / 2;
	if (i < mid) del_val(2 * v + 1, tl, mid, i);
	else del_val(2 * v + 2, mid, tr, i);
	t[v] = f(t[2 * v + 1], t[2 * v + 2]);
}

int get_res(int v, int tl, int tr, int l, int x) {
	l = max(l, tl);
	if (l >= tr || t[v].max < x) return -oo;
	if (l == tl && t[v].min >= x) return t[v].res;
	int mid = (tl + tr) / 2;
	return max(get_res(2 * v + 1, tl, mid, l, x), get_res(2 * v + 2, mid, tr, l, x));
}

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); del_val(0, 0, len(arr), GI(f.F));
		}
		else break;
		it = st.upper_bound(Mp(A1, oo));
	}
	st.insert(Mp(A1, A2)); set_val(0, 0, len(arr), GI(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;
	build(0, 0, len(arr));
	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;
		}
		ans = max(ans, A[i].F + get_res(0, 0, len(arr), GI(A[i].S.F) + 1, A[i].S.S + 1));
	}
	if (ans == 0) cout << -1 << endl;
	else cout << ans << endl;
}

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

	null.res = -oo; null.max = -oo; null.min = oo;

	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