Submission #772893

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
772893	2023-07-04T12:28:44 Z	raysh07	Team Contest (JOI22_team)	C++17	0 / 100	133 ms	15300 KB

team

#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[4 * 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 - 1, 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	1 ms	340 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 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	1 ms	340 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 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	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	133 ms	15300 KB	Output is correct
12	Incorrect	81 ms	9712 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	133 ms	15300 KB	Output is correct
12	Incorrect	81 ms	9712 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	133 ms	15300 KB	Output is correct
12	Incorrect	81 ms	9712 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #6

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	133 ms	15300 KB	Output is correct
12	Incorrect	81 ms	9712 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	1 ms	340 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 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	-