oj.uz

Submission #772897

# Submission time Handle Problem Language Result Execution time Memory
772897 2023-07-04T12:29:24 Z raysh07 Team Contest (JOI22_team) C++17
0 / 100
 134 ms 14400 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct info{
	int a, b, c;
};

const int N = 1.5e5 + 69;
int seg[4 * N][3], n;
int inv[N][3], tim = 0;

void upd(int l, int r, int pos, int qp, int v, int i){
	if (l == r){
		seg[pos][i] = max(seg[pos][i], v);
		return;
	}

	int mid = (l + r)/2;
	if (qp <= mid) upd(l, mid, pos*2, qp, v, i);
	else upd(mid + 1, r, pos*2 + 1, qp, v, i);

	seg[pos][i] = max(seg[pos * 2][i], seg[pos * 2 + 1][i]);
}

int query(int l, int r, int pos, int ql, int qr, int i){
	if (l >= ql && r <= qr) return seg[pos][i];
	else if (l > qr || r < ql) return 0;

	int mid = (l + r)/2;
	return max(query(l, mid, pos*2, ql, qr, i), query(mid + 1, r, pos*2 + 1, ql, qr, i));
}

void compress(vector <int> &a){
	set <int> st;
	map <int, int> mp;
	for (auto x : a) st.insert(x);

	int pr = 0;
	for (auto x : st) {
		mp[x] = ++pr;
		inv[pr][tim] = x;
	}
	tim++;
	for (auto &x : a) x = mp[x];
}

void Solve()
{
	cin >> n;

	vector <int> a(n), b(n), c(n);

	for (int i = 1; i <= n; i++){
		cin >> a[i - 1] >> b[i - 1] >> c[i - 1];
	}

	compress(a);
	compress(b);
	compress(c);

	vector <info> v(n);
	for (int i = 0; i < n; i++){
		v[i].a = a[i];
		v[i].b = b[i];
		v[i].c = c[i];
	}

	sort(v.begin(), v.end(), [&](info x, info y){
		return x.a < y.a;
	});

	vector <info> todo, good;

	//go in increasing a 
	//position stuff with c 
	//find max b possible 
	for (auto x : v){
		if (todo.size() && todo[0].a != x.a){
			for (auto y : todo){
				upd(1, n, 1, y.c, y.b, 0);
			}
			todo.clear();
		}

		int mxb = query(1, n, 1, 1, x.c, 0);
	//	cout << mxb << " ";
		if (mxb > x.b) {
			info ok;
			ok.a = x.a;
			ok.b = mxb;
			ok.c = x.c;
			good.push_back(ok);
		}
		todo.push_back(x);
	}
//	cout << "\n";
	todo.clear();
	sort(v.begin(), v.end(), [&](info x, info y){
		return x.b < y.b;
	});

	for (auto x : v){
		if (todo.size() && todo[0].b != x.b){
			for (auto y : todo){
				upd(1, n, 1, y.c, y.a, 1);
			}
			todo.clear();
		}

		int mxa = query(1, n, 1, 1, x.c, 0);
		if (mxa > x.a){
			info ok;
			ok.a = mxa;
			ok.b = x.b;
			ok.c = x.c;
			good.push_back(ok);
		}
		todo.push_back(x);
	}

	int ans = -1;
	
// 	for (auto x : good){
// 	    cout << x.a << " " << x.b << " " << x.c << "\n";
// 	}
	//sort by x, query only useful y 

	sort(good.begin(), good.end(), [&](info x, info y){
		return x.a < y.a;
	});

	sort(v.begin(), v.end(), [&](info x, info y){
		return x.a < y.a;
	});

	int ptr = 0;
	for (auto x : good){
		while (ptr != v.size() && v[ptr].a < x.a){
		  //  cout << "ADDED " << x.b << " " << x.c << "\n";
			upd(1, n, 1, v[ptr].b, v[ptr].c, 2);
			ptr++;
		}

		int mxc = query(1, n, 1, 1, x.b - 1, 2);
	//	cout << "QUERYING " << x.b << " " << x.c << "\n";
		if (mxc > x.c){
			ans = max(ans, inv[x.a][0] + inv[x.b][1] + inv[mxc][2]);
		}
	}

	cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Compilation message

team.cpp: In function 'void Solve()':
team.cpp:144:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |   while (ptr != v.size() && v[ptr].a < x.a){
      |          ~~~~^~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 134 ms 14400 KB Output is correct
12 Incorrect 84 ms 9220 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 134 ms 14400 KB Output is correct
12 Incorrect 84 ms 9220 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 134 ms 14400 KB Output is correct
12 Incorrect 84 ms 9220 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 134 ms 14400 KB Output is correct
12 Incorrect 84 ms 9220 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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