oj.uz

Submission #566176

# Submission time Handle Problem Language Result Execution time Memory
566176 2022-05-22T03:57:37 Z 8e7 Team Contest (JOI22_team) C++17
0 / 100
 53 ms 12872 KB 
//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];
	int tag[4 * maxn];
	
	void push(int cur, int l, int r) {
		if (!tag[cur]) return;
		z[cur] = tag[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]);
	}
	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];
			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, 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10324 KB Output is correct
2 Correct 4 ms 10196 KB Output is correct
3 Correct 5 ms 10324 KB Output is correct
4 Correct 5 ms 10300 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10308 KB Output is correct
7 Correct 6 ms 10196 KB Output is correct
8 Correct 5 ms 10196 KB Output is correct
9 Correct 7 ms 10268 KB Output is correct
10 Correct 5 ms 10196 KB Output is correct
11 Correct 5 ms 10324 KB Output is correct
12 Correct 5 ms 10308 KB Output is correct
13 Correct 5 ms 10308 KB Output is correct
14 Correct 5 ms 10324 KB Output is correct
15 Incorrect 5 ms 10316 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10324 KB Output is correct
2 Correct 4 ms 10196 KB Output is correct
3 Correct 5 ms 10324 KB Output is correct
4 Correct 5 ms 10300 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10308 KB Output is correct
7 Correct 6 ms 10196 KB Output is correct
8 Correct 5 ms 10196 KB Output is correct
9 Correct 7 ms 10268 KB Output is correct
10 Correct 5 ms 10196 KB Output is correct
11 Correct 5 ms 10324 KB Output is correct
12 Correct 5 ms 10308 KB Output is correct
13 Correct 5 ms 10308 KB Output is correct
14 Correct 5 ms 10324 KB Output is correct
15 Incorrect 5 ms 10316 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10196 KB Output is correct
2 Correct 5 ms 10200 KB Output is correct
3 Correct 5 ms 10196 KB Output is correct
4 Correct 5 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10324 KB Output is correct
7 Correct 6 ms 10304 KB Output is correct
8 Correct 5 ms 10248 KB Output is correct
9 Correct 7 ms 10196 KB Output is correct
10 Correct 5 ms 10196 KB Output is correct
11 Correct 53 ms 12872 KB Output is correct
12 Incorrect 34 ms 12192 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10196 KB Output is correct
2 Correct 5 ms 10200 KB Output is correct
3 Correct 5 ms 10196 KB Output is correct
4 Correct 5 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10324 KB Output is correct
7 Correct 6 ms 10304 KB Output is correct
8 Correct 5 ms 10248 KB Output is correct
9 Correct 7 ms 10196 KB Output is correct
10 Correct 5 ms 10196 KB Output is correct
11 Correct 53 ms 12872 KB Output is correct
12 Incorrect 34 ms 12192 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10196 KB Output is correct
2 Correct 5 ms 10200 KB Output is correct
3 Correct 5 ms 10196 KB Output is correct
4 Correct 5 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10324 KB Output is correct
7 Correct 6 ms 10304 KB Output is correct
8 Correct 5 ms 10248 KB Output is correct
9 Correct 7 ms 10196 KB Output is correct
10 Correct 5 ms 10196 KB Output is correct
11 Correct 53 ms 12872 KB Output is correct
12 Incorrect 34 ms 12192 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10196 KB Output is correct
2 Correct 5 ms 10200 KB Output is correct
3 Correct 5 ms 10196 KB Output is correct
4 Correct 5 ms 10196 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10324 KB Output is correct
7 Correct 6 ms 10304 KB Output is correct
8 Correct 5 ms 10248 KB Output is correct
9 Correct 7 ms 10196 KB Output is correct
10 Correct 5 ms 10196 KB Output is correct
11 Correct 53 ms 12872 KB Output is correct
12 Incorrect 34 ms 12192 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10324 KB Output is correct
2 Correct 4 ms 10196 KB Output is correct
3 Correct 5 ms 10324 KB Output is correct
4 Correct 5 ms 10300 KB Output is correct
5 Correct 5 ms 10196 KB Output is correct
6 Correct 5 ms 10308 KB Output is correct
7 Correct 6 ms 10196 KB Output is correct
8 Correct 5 ms 10196 KB Output is correct
9 Correct 7 ms 10268 KB Output is correct
10 Correct 5 ms 10196 KB Output is correct
11 Correct 5 ms 10324 KB Output is correct
12 Correct 5 ms 10308 KB Output is correct
13 Correct 5 ms 10308 KB Output is correct
14 Correct 5 ms 10324 KB Output is correct
15 Incorrect 5 ms 10316 KB Output isn't correct
16 Halted 0 ms 0 KB -