oj.uz

Submission #892300

# Submission time Handle Problem Language Result Execution time Memory
892300 2023-12-25T07:00:47 Z vjudge1 Team Contest (JOI22_team) C++17
0 / 100
 60 ms 27000 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 998244353;
const int N = 2e5;




struct ST{
	vector<int > tree;
	int n;
	
	ST(int sz){
		n = N;
		tree.resize(4 * n, -1);
	};
	
	int merge(int A, int B){
		return max(A, B);
		/*vector<int> v = {A.ff, A.ss, B.ff, B.ss};
		sort(all(v));
		return {v[3], v[2]};
		* */
	}
	
	void update(int pos, int x, int v, int vl, int vr){
		if(vl == vr){
			tree[v] = max(tree[v], x);
		}else{
			int mid =(vl + vr)>>1;
			if(mid >= pos) update(pos, x, v<<1, vl, mid);
			else update(pos, x, v<<1|1, mid+1, vr);
			tree[v] = merge(tree[v<<1], tree[v<<1|1]);
		}
	};
	
	int get_max(int l, int r, int v, int vl, int vr){
		if(l > vr or vl > r) return -1;
		if(l <= vl and r >= vr) return tree[v];
		int mid = (vl + vr)>>1;
		return merge(get_max(l, r, v<<1, vl, mid), get_max(l, r, v<<1|1, mid+1, vr));
	}
	
};





int n;
int cX[N+10], cY[N+10], cZ[N+10];
void compr(auto &x, auto &y, auto &z){
	vector<int> vec;
	for(int i = 0;i < n; i++) vec.push_back(x[i]);
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	
	for(int i = 0;i < n; i++){
		int it = lower_bound(all(vec), x[i]) - vec.begin() + 1;
		cX[it] = x[i];
		x[i] = it;
	}
	vec.clear();
	for(int i = 0;i < n; i++) vec.push_back(y[i]);
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	
	for(int i = 0;i < n; i++){
		int it = lower_bound(all(vec), y[i]) - vec.begin() + 1;
		cY[it] = y[i];
		y[i] = it;
	}
	vec.clear();
	for(int i = 0;i < n; i++) vec.push_back(z[i]);
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	for(int i = 0;i < n; i++){
		int it = lower_bound(all(vec), z[i]) - vec.begin() + 1;
		cZ[it] = z[i];
		z[i] = it;
	}
}






signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	vector<int> x(n), y(n), z(n);
	for(int i = 0;i < n; i++){
		cin >> x[i] >> y[i] >> z[i];
	}
	auto get=[&](auto x, auto y, auto z){
		compr(x, y, z);
		vector<int> p(n);
		int res = -1;
		iota(all(p), 0);
		sort(all(p), [&](int i, int j){
			return x[i] < x[j];
		});
		ST seg(N);
		auto chmax = [&](auto &A, auto B){
			if(B.ff + B.ss > A.ff + A.ss) A = B;
			else if(B.ff + B.ss == A.ff + A.ss && A.ff < B.ff){
				A = B;
			}
		};
		for(int i : p){
			//cout << x[i] << " " <<  y[i] << " " << z[i] << '\n';
			//cout << cX[x[i]] << ' ' << cY[y[i]] << ' ' << cZ[z[i]] << '\n';
		}
		vector<pair<int, int>> pref;
		for(int i : p){
		//	cout << cX[x[i]] << ' ' << cY[y[i]] << ' ' << cZ[z[i]] << "   =   ";
			pair<int, int> cur = {INT_MIN, INT_MIN};
			if(pref.empty() == false) cur = pref.back();
			int Z = seg.get_max(1, y[i]-1, 1, 1, N);
			if(Z > z[i]){
				chmax(cur, make_pair(cY[y[i]], cZ[Z]));
			}
			pref.push_back(cur);
		//	cout << cur.ff << ' ' << cur.ss << '\n';
			seg.update(y[i], z[i], 1, 1, N);
		}
		for(int i = 0;i < n; ){
		//	cout << i+1 << " = ";
			int j = i;
			for(j = i; j <n && x[p[i]] == x[p[j]]; j++){
				if(i == 0){
					continue;
				}
				int fnY = pref[i-1].ff;
				int fnZ = pref[i-1].ss;
				if(fnY > cY[y[p[j]]] && fnZ > cZ[z[p[j]]]){
					res = max(res, cX[x[p[j]]] + fnY + fnZ);
				}
			}
		//	cout << j << '\n';
			i = j;
		}
		return res;
	};
	int ALL = -1;
	ALL = max(get(x, y, z), ALL);
	// ALL = max(get(x, z, y), ALL);
	//ALL = max(get(z, x, y), ALL);
	//ALL = max(get(z, y, z), ALL);
	cout << ALL;
	return 0;
}

Compilation message

team.cpp:57:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   57 | void compr(auto &x, auto &y, auto &z){
      |            ^~~~
team.cpp:57:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   57 | void compr(auto &x, auto &y, auto &z){
      |                     ^~~~
team.cpp:57:30: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   57 | void compr(auto &x, auto &y, auto &z){
      |                              ^~~~
team.cpp: In instantiation of 'main()::<lambda(auto:26, auto:27, auto:28)> [with auto:26 = std::vector<long long int>; auto:27 = std::vector<long long int>; auto:28 = std::vector<long long int>]':
team.cpp:153:23:   required from here
team.cpp:117:11: warning: unused variable 'i' [-Wunused-variable]
  117 |   for(int i : p){
      |           ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10840 KB Output is correct
11 Correct 3 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 2 ms 11096 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 3 ms 10844 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 3 ms 10840 KB Output is correct
25 Incorrect 2 ms 10844 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10840 KB Output is correct
11 Correct 3 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 2 ms 11096 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 3 ms 10844 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 3 ms 10840 KB Output is correct
25 Incorrect 2 ms 10844 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10788 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 60 ms 27000 KB Output is correct
12 Incorrect 40 ms 19392 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10788 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 60 ms 27000 KB Output is correct
12 Incorrect 40 ms 19392 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10788 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 60 ms 27000 KB Output is correct
12 Incorrect 40 ms 19392 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10788 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10588 KB Output is correct
11 Correct 60 ms 27000 KB Output is correct
12 Incorrect 40 ms 19392 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 10840 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 2 ms 10588 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10840 KB Output is correct
11 Correct 3 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Correct 2 ms 10588 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 2 ms 11096 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 3 ms 10844 KB Output is correct
23 Correct 2 ms 10844 KB Output is correct
24 Correct 3 ms 10840 KB Output is correct
25 Incorrect 2 ms 10844 KB Output isn't correct
26 Halted 0 ms 0 KB -