Submission #887617

#	Time	Username	Problem	Language	Result	Execution time	Memory
887617		MinaRagy06	Team Contest (JOI22_team)	C++17	100 / 100	315 ms	119720 KiB

team

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1) 

const int inf = 1e9;
int y = -1, mncnt = 2, mxcnt = 2;
struct nodemn {
	int l, r, v;
	nodemn() {l = 0, r = 0, v = 1e9;}
} segmn[5'000'005];
struct nodemx {
	int l, r, v;
	nodemx() {l = 0, r = 0, v = -1e9;}
} segmx[5'000'005];
void updmn(int i, int l, int r, int x, int v) {
	if (l == r) {
		segmn[i].v = min(segmn[i].v, v);
		return;
	}
	if (x <= md) {
		if (!segmn[i].l) {
			segmn[i].l = mncnt++;
		}
		updmn(segmn[i].l, l, md, x, v);
	} else {
		if (!segmn[i].r) {
			segmn[i].r = mncnt++;
		}
		updmn(segmn[i].r, md + 1, r, x, v);
	}
	segmn[i].v = min(segmn[segmn[i].l].v, segmn[segmn[i].r].v);
}
void updmx(int i, int l, int r, int x, int v) {
	if (l == r) {
		segmx[i].v = max(segmx[i].v, v);
		return;
	}
	if (x <= md) {
		if (!segmx[i].l) {
			segmx[i].l = mxcnt++;
		}
		updmx(segmx[i].l, l, md, x, v);
	} else {
		if (!segmx[i].r) {
			segmx[i].r = mxcnt++;
		}
		updmx(segmx[i].r, md + 1, r, x, v);
	}
	segmx[i].v = max(segmx[segmx[i].l].v, segmx[segmx[i].r].v);
}
int getmn(int i, int l, int r, int s, int e) {
	if (i == 0 || r < s || e < l) {
		return 1e9;
	}
	if (s <= l && r <= e) {
		return segmn[i].v;
	}
	return min(getmn(segmn[i].l, l, md, s, e), getmn(segmn[i].r, md + 1, r, s, e));
}
int getmx(int i, int l, int r, int s, int e) {
	if (i == 0 || r < s || e < l) {
		return -1e9;
	}
	if (s <= l && r <= e) {
		return segmx[i].v;
	}
	return max(getmx(segmx[i].l, l, md, s, e), getmx(segmx[i].r, md + 1, r, s, e));
}
int get(int i, int l, int r, int s, int e, int k) {
	if (l == r) {
		return l;
	}
	if (md + 1 <= e && segmn[segmn[i].r].v < k) {
		return get(segmn[i].r, md + 1, r, s, e, k);
	} else {
		return get(segmn[i].l, l, md, s, e, k);
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	array<int, 3> a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2];
	}
	sort(a, a + n);
	int ans = -1;
	int cur = 0;
	for (int i = 0; i < n; i++) {
		while (a[cur][0] < a[i][0]) {
			updmn(1, 0, 1e8, a[cur][1], a[cur][2]);
			updmx(1, 0, 1e8, a[cur][1], a[cur][2]);
			if (getmx(1, 0, 1e8, 0, a[cur][1] - 1) > a[cur][2]) {
				y = max(y, a[cur][1]);
			}
			if (a[cur][1] + 1 != int(1e8) && getmn(1, 0, 1e8, a[cur][1] + 1, 1e8) < a[cur][2]) {
				int newy = get(1, 0, 1e8, a[cur][1] + 1, 1e8, a[cur][2]);
				y = max(y, newy);
			}
			cur++;
		}
// 		while (a[cur][0] < a[i][0]) {
// 			mx[a[cur][1]] = max(mx[a[cur][1]], a[cur][2]);
// 			mn[a[cur][1]] = min(mn[a[cur][1]], a[cur][2]);
// 			for (int newy = 304; newy > a[cur][1]; newy--) {
// 				if (mn[newy] < a[cur][2]) {
// 					y = max(y, newy);
// 					break;
// 				}
// 			}
// 			for (int newy = 0; newy < a[cur][1]; newy++) {
// 				if (mx[newy] > a[cur][2]) {
// 					y = max(y, a[cur][1]);
// 					break;
// 				}
// 			}
// 			cur++;
// 		}
		if (y >= max(1, a[i][1] + 1)) {
			int z = getmx(1, 0, 1e8, 0, y - 1);
			if (a[i][2] < z) {
				ans = max(ans, a[i][0] + z + y);
			}
		}
	}
	cout << ans << '\n';
	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