Submission #926825

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
926825	2024-02-13T20:44:53 Z	OAleksa	Team Contest (JOI22_team)	C++14	0 / 100	2000 ms	1048580 KB

team

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int N = 2e5 + 69;
const int A = 4010;
const int inf = 1e9;
vector<vector<int>> st(A, vector<int>(4 * A, inf));
int n, a[N], b[N], c[N], d[A][A], mn[A][A];
int gmx[A][A], gmn[A][A];
void Modify(int v, int tl, int tr, int r, int p, int x) {
	if (tl == tr)
		st[r][v] = min(st[r][v], x);
	else {
		int mid = (tl + tr) / 2;
		if (p <= mid)
			Modify(v * 2, tl, mid, r, p, x);
		else
			Modify(v * 2 + 1, mid + 1, tr, r, p, x);
		st[r][v] = min(st[r][v * 2], st[r][v * 2 + 1]);
	}
}
int Get(int v, int tl, int tr, int L, int R, int r, int x) {
	if (tl > R || tr < L)
		return inf;
	else if (tl == tr)
		return tl;
	else {
		int mid = (tl + tr) / 2;
		if (st[r][v * 2 + 1] < x)
			return Get(v * 2 + 1, mid + 1, tr, L, R, r, x);
		else
			return Get(v * 2, tl, mid, L, R, r, x);
	}
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n;
  	for (int i = 1;i <= n;i++)
  		cin >> a[i] >> b[i] >> c[i];
  	for (int i = 0;i < A;i++) {
  		for (int j = 0;j < A;j++) {
  			gmn[i][j] = inf;
  			gmx[i][j] = -inf;
  			d[i][j] = -inf;
  			mn[i][j] = inf;
  		}
  	}
  	for (int i = 1;i <= n;i++) {
  		gmx[a[i]][b[i]] = max(c[i], gmx[a[i]][b[i]]);
  		gmn[a[i]][b[i]] = min(c[i], gmn[a[i]][b[i]]);
  		Modify(1, 1, A, a[i], b[i], c[i]);
  	}
  	for (int i = 1;i < A;i++) {
  		for (int j = 1;j < A;j++)
  			d[i][j] = max({d[i][j - 1], d[i - 1][j], gmx[i][j]});
  	}
  	int ans = -1;
  	for (int i = 1;i <= n;i++) {
  		for (int j = a[i] - 1;j >= 1;j--) {
  			int y = Get(1, 1, A, b[i] + 1, A, j, d[j][b[i]]);
  			if (y != inf && gmn[j][y] < d[j][b[i]]) {
  				ans = max(ans, a[i] + y + d[j][b[i]]);
  			}
  		}
  	}
  	cout << ans << '\n';
  }
  return 0;
}

Subtask #1

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	456 ms	1011120 KB	Output is correct
2	Correct	348 ms	1011024 KB	Output is correct
3	Correct	346 ms	1011128 KB	Output is correct
4	Correct	356 ms	1011284 KB	Output is correct
5	Correct	347 ms	1011028 KB	Output is correct
6	Correct	352 ms	1011276 KB	Output is correct
7	Correct	347 ms	1011024 KB	Output is correct
8	Correct	352 ms	1011224 KB	Output is correct
9	Correct	360 ms	1011028 KB	Output is correct
10	Correct	354 ms	1011248 KB	Output is correct
11	Correct	372 ms	1011024 KB	Output is correct
12	Correct	367 ms	1011024 KB	Output is correct
13	Correct	445 ms	1011392 KB	Output is correct
14	Execution timed out	2614 ms	1048580 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	456 ms	1011120 KB	Output is correct
2	Correct	348 ms	1011024 KB	Output is correct
3	Correct	346 ms	1011128 KB	Output is correct
4	Correct	356 ms	1011284 KB	Output is correct
5	Correct	347 ms	1011028 KB	Output is correct
6	Correct	352 ms	1011276 KB	Output is correct
7	Correct	347 ms	1011024 KB	Output is correct
8	Correct	352 ms	1011224 KB	Output is correct
9	Correct	360 ms	1011028 KB	Output is correct
10	Correct	354 ms	1011248 KB	Output is correct
11	Correct	372 ms	1011024 KB	Output is correct
12	Correct	367 ms	1011024 KB	Output is correct
13	Correct	445 ms	1011392 KB	Output is correct
14	Execution timed out	2614 ms	1048580 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #3

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	426 ms	1011188 KB	Output is correct
2	Correct	351 ms	1011316 KB	Output is correct
3	Correct	354 ms	1011028 KB	Output is correct
4	Correct	351 ms	1011028 KB	Output is correct
5	Correct	375 ms	1011284 KB	Output is correct
6	Correct	363 ms	1011028 KB	Output is correct
7	Correct	353 ms	1011136 KB	Output is correct
8	Correct	350 ms	1011024 KB	Output is correct
9	Correct	347 ms	1011024 KB	Output is correct
10	Correct	349 ms	1011028 KB	Output is correct
11	Correct	381 ms	1012816 KB	Output is correct
12	Incorrect	368 ms	1011972 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	426 ms	1011188 KB	Output is correct
2	Correct	351 ms	1011316 KB	Output is correct
3	Correct	354 ms	1011028 KB	Output is correct
4	Correct	351 ms	1011028 KB	Output is correct
5	Correct	375 ms	1011284 KB	Output is correct
6	Correct	363 ms	1011028 KB	Output is correct
7	Correct	353 ms	1011136 KB	Output is correct
8	Correct	350 ms	1011024 KB	Output is correct
9	Correct	347 ms	1011024 KB	Output is correct
10	Correct	349 ms	1011028 KB	Output is correct
11	Correct	381 ms	1012816 KB	Output is correct
12	Incorrect	368 ms	1011972 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	426 ms	1011188 KB	Output is correct
2	Correct	351 ms	1011316 KB	Output is correct
3	Correct	354 ms	1011028 KB	Output is correct
4	Correct	351 ms	1011028 KB	Output is correct
5	Correct	375 ms	1011284 KB	Output is correct
6	Correct	363 ms	1011028 KB	Output is correct
7	Correct	353 ms	1011136 KB	Output is correct
8	Correct	350 ms	1011024 KB	Output is correct
9	Correct	347 ms	1011024 KB	Output is correct
10	Correct	349 ms	1011028 KB	Output is correct
11	Correct	381 ms	1012816 KB	Output is correct
12	Incorrect	368 ms	1011972 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #6

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	426 ms	1011188 KB	Output is correct
2	Correct	351 ms	1011316 KB	Output is correct
3	Correct	354 ms	1011028 KB	Output is correct
4	Correct	351 ms	1011028 KB	Output is correct
5	Correct	375 ms	1011284 KB	Output is correct
6	Correct	363 ms	1011028 KB	Output is correct
7	Correct	353 ms	1011136 KB	Output is correct
8	Correct	350 ms	1011024 KB	Output is correct
9	Correct	347 ms	1011024 KB	Output is correct
10	Correct	349 ms	1011028 KB	Output is correct
11	Correct	381 ms	1012816 KB	Output is correct
12	Incorrect	368 ms	1011972 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #7

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	456 ms	1011120 KB	Output is correct
2	Correct	348 ms	1011024 KB	Output is correct
3	Correct	346 ms	1011128 KB	Output is correct
4	Correct	356 ms	1011284 KB	Output is correct
5	Correct	347 ms	1011028 KB	Output is correct
6	Correct	352 ms	1011276 KB	Output is correct
7	Correct	347 ms	1011024 KB	Output is correct
8	Correct	352 ms	1011224 KB	Output is correct
9	Correct	360 ms	1011028 KB	Output is correct
10	Correct	354 ms	1011248 KB	Output is correct
11	Correct	372 ms	1011024 KB	Output is correct
12	Correct	367 ms	1011024 KB	Output is correct
13	Correct	445 ms	1011392 KB	Output is correct
14	Execution timed out	2614 ms	1048580 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-