Submission #549132

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
549132	2022-04-15T09:10:34 Z	hohohaha	Team Contest (JOI22_team)	C++14	0 / 100	2000 ms	29156 KB

team

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

#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define em emplace
#define sp ' ' 
#define endl '\n'
#define int long long

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count()); 

int rint(int l, int r) { 
	return rng() % (r - l + 1) + l; 
}

const int maxn = 2e5 + 5, inf = LLONG_MAX / 100ll; 

struct it { 
	vector<int> x, z, m; 
	it(int n) { 
		x = z = m = vi(n + 1 << 2, -inf);
	}
	void upd_x(int u, int l, int r, int p, int v) { 
		if(l > p or p > r) return; 
		if(l == r) { 
			x[u] = max(x[u], v); 
		}
		else { 
			int mid = l + r >> 1; 
			upd_x(u << 1, l, mid, p, v); 
			upd_x(u << 1 | 1, mid + 1, r, p, v); 
			x[u] = max(x[u << 1], x[u << 1 | 1]);
			m[u] = max(max(m[u << 1], m[u << 1 | 1]), x[u] + z[u << 1 | 1]); 
		}
	}
	void upd_z(int u, int l, int r, int p, int v) { 
		if(l > p or p > r) return; 
		if(l == r) { 
			z[u] = max(z[u], v); 
		}
		else { 
			int mid = l + r >> 1; 
			upd_z(u << 1, l, mid, p, v); 
			upd_z(u << 1 | 1, mid + 1, r, p, v); 
			z[u] = max(z[u << 1], z[u << 1 | 1]);
			m[u] = max(max(m[u << 1], m[u << 1 | 1]), x[u] + z[u << 1 | 1]); 
		}
	}
	int get_x(int u, int l, int r, int ll, int rr) { 
		if(l > rr or ll > r) return -inf;
		if(ll <= l and r <= rr) return x[u]; 
		else { 
		 	int mid = l + r >> 1; 
		 	return max(get_x(u << 1, l, mid, ll, rr), get_x(u << 1 | 1, mid + 1, r, ll, rr)); 
		 }
	}
	int get_z(int u, int l, int r, int ll, int rr) { 
		if(l > rr or ll > r) return -inf;
		if(ll <= l and r <= rr) return z[u]; 
		else { 
		 	int mid = l + r >> 1; 
		 	return max(get_z(u << 1, l, mid, ll, rr), get_z(u << 1 | 1, mid + 1, r, ll, rr)); 
		 }
	}
	pair<int, ii> get(int u, int l, int r, int ll, int rr) { 
		if(l > rr or ll > r) return make_pair(-inf,ii(-inf, -inf)); 
		if(ll <= l and r <= rr) return make_pair(m[u], ii(x[u], z[u]));
		int mid = l + r >> 1; 
		auto tl = get(u << 1, l, mid, ll, rr); 
		auto tr = get(u << 1 | 1, mid + 1, r, ll, rr);
		return make_pair(max(max(tl.fi, tr.fi), tl.se.fi + tr.se.se), ii(max(tl.se.fi, tr.se.fi), max(tl.se.se, tr.se.se))); 
	}
}; 


int n; 
int x[maxn], y[maxn], z[maxn]; 
int fx[maxn], fy[maxn], fz[maxn]; 
vector<int> pts_x[maxn]; 
vector<int> pts_y[maxn];
int ans = -inf; 

void solve(int l, int r) { 
//	cout << l << sp << r << endl; 
	int mid = l + r >> 1; 
	if(l < r) { 
		solve(l, mid); 
		solve(mid + 1, r); 
	}
	
	vector<int> pts; 
	fori(x, l, r) for(int i: pts_x[x]) pts.eb(i); 
	sort(begin(pts), end(pts), [] (int i, int j) { return z[i] < z[j]; });
	int m = 1; 
	fori(itr, 0, pts.size() - 1) { 
		if(itr and z[pts[itr]] > z[pts[itr - 1]]) ++m; 
		fz[pts[itr]] = m; 
	}
	sort(begin(pts),end(pts), [] (int i, int j) { return y[i] < y[j]; }); 
	m = 1; 
	fori(itr, 0, pts.size() - 1) { 
		if(itr and y[pts[itr]] > y[pts[itr - 1]]) ++m; 
		fy[pts[itr]] = m; 
	}
	for(int i: pts) pts_y[fy[i]].eb(i); 
	
	it IT(pts.size()); 
	
	fori(y, 1, pts.size()) { 
		for(int i: pts_y[y]) { 
			if(fx[i] <= mid) ans = max(ans, max(IT.get_x(1, 1, pts.size(), 1, fz[i] - 1) + IT.get_z(1, 1, pts.size(), fz[i] + 1, pts.size()), 
												IT.get(1, 1, pts.size(), fz[i], pts.size()).fi)
											+ ::	y[i]);
		}
		for(int i: pts_y[y]) {
			if(fx[i] > mid) IT.upd_x(1, 1, pts.size(), fz[i], x[i]); 
			else IT.upd_z(1, 1, pts.size(), fz[i], z[i]); 
		}
	}
}

signed main() { 
//	ios_base::sync_with_stdio(0); 
//	cin.tie(0); 
//	cout.tie(0); 
	
	cin >> n; 
	fori(i, 1, n) { 
		cin >> x[i] >> y[i] >> z[i]; 
	}
	vector<int> alx; 
	fori(i, 1, n) alx.eb(x[i]); 
	sort(begin(alx), end(alx)); 
	fori(i, 1, n) fx[i] = lower_bound(begin(alx), end(alx), x[i]) - begin(alx) + 1; 
	fori(i, 1, n) pts_x[fx[i]].eb(i); 
	solve(1, n); 
	
	ans = max(ans, -1ll); 
	cout << ans; 
}

Compilation message

team.cpp: In constructor 'it::it(long long int)':
team.cpp:27:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   27 |   x = z = m = vi(n + 1 << 2, -inf);
      |                  ~~^~~
team.cpp: In member function 'void it::upd_x(long long int, long long int, long long int, long long int, long long int)':
team.cpp:35:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |    int mid = l + r >> 1;
      |              ~~^~~
team.cpp: In member function 'void it::upd_z(long long int, long long int, long long int, long long int, long long int)':
team.cpp:48:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |    int mid = l + r >> 1;
      |              ~~^~~
team.cpp: In member function 'long long int it::get_x(long long int, long long int, long long int, long long int, long long int)':
team.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = l + r >> 1;
      |               ~~^~~
team.cpp: In member function 'long long int it::get_z(long long int, long long int, long long int, long long int, long long int)':
team.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int mid = l + r >> 1;
      |               ~~^~~
team.cpp: In member function 'std::pair<long long int, std::pair<long long int, long long int> > it::get(long long int, long long int, long long int, long long int, long long int)':
team.cpp:74:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int mid = l + r >> 1;
      |             ~~^~~
team.cpp: In function 'void solve(long long int, long long int)':
team.cpp:91:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	6 ms	9684 KB	Output is correct
7	Correct	5 ms	9684 KB	Output is correct
8	Correct	5 ms	9684 KB	Output is correct
9	Correct	5 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	5 ms	9708 KB	Output is correct
13	Correct	5 ms	9684 KB	Output is correct
14	Correct	11 ms	9812 KB	Output is correct
15	Incorrect	10 ms	9812 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	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	5 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	6 ms	9684 KB	Output is correct
7	Correct	5 ms	9684 KB	Output is correct
8	Correct	5 ms	9684 KB	Output is correct
9	Correct	5 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	5 ms	9708 KB	Output is correct
13	Correct	5 ms	9684 KB	Output is correct
14	Correct	11 ms	9812 KB	Output is correct
15	Incorrect	10 ms	9812 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	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	6 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	6 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	6 ms	9684 KB	Output is correct
8	Correct	6 ms	9684 KB	Output is correct
9	Correct	5 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Execution timed out	2087 ms	29156 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	6 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	6 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	6 ms	9684 KB	Output is correct
8	Correct	6 ms	9684 KB	Output is correct
9	Correct	5 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Execution timed out	2087 ms	29156 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	6 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	6 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	6 ms	9684 KB	Output is correct
8	Correct	6 ms	9684 KB	Output is correct
9	Correct	5 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Execution timed out	2087 ms	29156 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #6

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	6 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	6 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	6 ms	9684 KB	Output is correct
8	Correct	6 ms	9684 KB	Output is correct
9	Correct	5 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Execution timed out	2087 ms	29156 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #7

0 / 27.0

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