Submission #566187

#	Time	Username	Problem	Language	Result	Execution time	Memory
566187		8e7	Team Contest (JOI22_team)	C++17	100 / 100	311 ms	25820 KiB

team

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 150005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
struct segtree{
	pii seg[4 * maxn];
	int z[4 * maxn], minz[maxn], type[4 * maxn];
	int tag[4 * maxn];
	
	void push(int cur, int l, int r) {
		if (!tag[cur]) return;
		z[cur] = tag[cur];
		if (type[cur]) seg[cur].ff = z[cur];
		if (r - l > 1) {
			tag[cur*2] = tag[cur];
			tag[cur*2+1] = tag[cur];
		}
		tag[cur] = 0;
	}
	void pull(int cur, int l, int r) {
		int mid = (l + r) / 2;
		push(cur*2, l, mid), push(cur*2+1, mid, r);	
		seg[cur] = max(seg[cur*2], seg[cur*2+1]);	
		z[cur] = max(z[cur*2], z[cur*2+1]);
		type[cur] = type[cur*2] | type[cur*2+1];
	}
	void init(int cur, int l, int r) {
		if (r <= l) return;
		if (r - l == 1) {
			seg[cur] = {0, l};
			minz[l] = inf;
			return;
		}
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur*2+1, m, r);
		pull(cur, l, r);
	}
	void modify(int cur, int l, int r, int ql, int qr, int val) {
		if (r <= l || ql >= r || qr <= l) return;	
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			tag[cur] = val;	
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, val);
		modify(cur*2+1, m, r, ql, qr, val);
		pull(cur, l, r);
	}
	void ch(int cur, int l, int r, int ind) {
		if (r <= l) return;	
		push(cur, l, r);
		if (r - l == 1) {
			if (z[cur] > minz[l]) {
				seg[cur].ff = z[cur];
				type[cur] = 1;
			}
			return;
		}
		int m = (l + r) / 2;
		if (ind < m) ch(cur*2, l, m, ind);
		else ch(cur*2+1, m, r, ind);
		pull(cur, l, r);
	}
	int search(int cur, int l, int r, int v) { //smallest index with z[x] >= v
		if (r <= l) return 0;	
		push(cur, l, r);
		if (r - l == 1) {
			if (z[cur] < v) return l+1;
			else return l;
		}
		int m = (l + r) / 2;
		if (z[cur*2] >= v) return search(cur*2, l, m, v);
		else return search(cur*2+1, m, r, v);
	}
	pii query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return {-1, 0};
		push(cur, l, r);
		if (ql <= l && qr >= r) return seg[cur];
		int m = (l + r) / 2;
		return max(query(cur*2, l, m, ql, qr), query(cur*2+1, m, r, ql, qr));
	}
} tr;
struct obj{
	int x, y, z;
	obj(){x = y = z = 0;}
	obj(int a, int b, int c){x = a, y = b, z = c;}
} a[maxn];
vector<int> xv, yv;
vector<int> ev[maxn];
int main() {
	io
	int n;
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> a[i].x >> a[i].y >> a[i].z;
		xv.push_back(a[i].x);
		yv.push_back(a[i].y);
	}
	sort(xv.begin(), xv.end());
	sort(yv.begin(), yv.end());
	xv.resize(int(unique(xv.begin(), xv.end()) - xv.begin()));
	yv.resize(int(unique(yv.begin(), yv.end()) - yv.begin()));
	for (int i = 0;i < n;i++) {
		a[i].x = lower_bound(xv.begin(), xv.end(), a[i].x) - xv.begin();
		a[i].y = lower_bound(yv.begin(), yv.end(), a[i].y) - yv.begin();
		ev[a[i].x].push_back(i);
	}
	int ans = -1;
	int siz = yv.size();
	tr.init(1, 0, siz);
	for (int it = 0;it < n;it++) {
		for (int i:ev[it]) {
			pii best = tr.query(1, 0, siz, a[i].y+1, siz);	
			if (best.ff != -1 && best.ff > a[i].z) {
				ans = max(ans, xv[a[i].x] + yv[best.ss] + best.ff);
			}
		}
		for (int i:ev[it]) {
			int z = a[i].z;
			int rig = tr.search(1, 0, siz, z);
			tr.modify(1, 0, siz, a[i].y + 1, rig, z);
			tr.minz[a[i].y] = min(tr.minz[a[i].y], z);
			tr.ch(1, 0, siz, a[i].y); 
			tr.ch(1, 0, siz, rig-1);
		}
	}
	cout << ans << "\n";
}

• 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