oj.uz

Submission #926826

# Submission time Handle Problem Language Result Execution time Memory
926826 2024-02-13T20:47:25 Z OAleksa Team Contest (JOI22_team) C++14
0 / 100
 2000 ms 1048584 KB 
#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 - 1, 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 - 1, 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 448 ms 1011184 KB Output is correct
2 Correct 353 ms 1011248 KB Output is correct
3 Correct 372 ms 1011036 KB Output is correct
4 Correct 356 ms 1011452 KB Output is correct
5 Correct 353 ms 1011024 KB Output is correct
6 Correct 368 ms 1011016 KB Output is correct
7 Correct 352 ms 1011028 KB Output is correct
8 Correct 364 ms 1011076 KB Output is correct
9 Correct 350 ms 1011108 KB Output is correct
10 Correct 353 ms 1011024 KB Output is correct
11 Correct 363 ms 1011024 KB Output is correct
12 Correct 363 ms 1011148 KB Output is correct
13 Correct 350 ms 1010980 KB Output is correct
14 Execution timed out 2566 ms 1048584 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 1011184 KB Output is correct
2 Correct 353 ms 1011248 KB Output is correct
3 Correct 372 ms 1011036 KB Output is correct
4 Correct 356 ms 1011452 KB Output is correct
5 Correct 353 ms 1011024 KB Output is correct
6 Correct 368 ms 1011016 KB Output is correct
7 Correct 352 ms 1011028 KB Output is correct
8 Correct 364 ms 1011076 KB Output is correct
9 Correct 350 ms 1011108 KB Output is correct
10 Correct 353 ms 1011024 KB Output is correct
11 Correct 363 ms 1011024 KB Output is correct
12 Correct 363 ms 1011148 KB Output is correct
13 Correct 350 ms 1010980 KB Output is correct
14 Execution timed out 2566 ms 1048584 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 1011228 KB Output is correct
2 Correct 390 ms 1011212 KB Output is correct
3 Correct 358 ms 1011560 KB Output is correct
4 Correct 355 ms 1010996 KB Output is correct
5 Correct 366 ms 1011252 KB Output is correct
6 Correct 351 ms 1010996 KB Output is correct
7 Correct 357 ms 1011280 KB Output is correct
8 Correct 351 ms 1011024 KB Output is correct
9 Correct 350 ms 1011336 KB Output is correct
10 Correct 349 ms 1011032 KB Output is correct
11 Correct 389 ms 1012120 KB Output is correct
12 Incorrect 378 ms 1011588 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 1011228 KB Output is correct
2 Correct 390 ms 1011212 KB Output is correct
3 Correct 358 ms 1011560 KB Output is correct
4 Correct 355 ms 1010996 KB Output is correct
5 Correct 366 ms 1011252 KB Output is correct
6 Correct 351 ms 1010996 KB Output is correct
7 Correct 357 ms 1011280 KB Output is correct
8 Correct 351 ms 1011024 KB Output is correct
9 Correct 350 ms 1011336 KB Output is correct
10 Correct 349 ms 1011032 KB Output is correct
11 Correct 389 ms 1012120 KB Output is correct
12 Incorrect 378 ms 1011588 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 1011228 KB Output is correct
2 Correct 390 ms 1011212 KB Output is correct
3 Correct 358 ms 1011560 KB Output is correct
4 Correct 355 ms 1010996 KB Output is correct
5 Correct 366 ms 1011252 KB Output is correct
6 Correct 351 ms 1010996 KB Output is correct
7 Correct 357 ms 1011280 KB Output is correct
8 Correct 351 ms 1011024 KB Output is correct
9 Correct 350 ms 1011336 KB Output is correct
10 Correct 349 ms 1011032 KB Output is correct
11 Correct 389 ms 1012120 KB Output is correct
12 Incorrect 378 ms 1011588 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 1011228 KB Output is correct
2 Correct 390 ms 1011212 KB Output is correct
3 Correct 358 ms 1011560 KB Output is correct
4 Correct 355 ms 1010996 KB Output is correct
5 Correct 366 ms 1011252 KB Output is correct
6 Correct 351 ms 1010996 KB Output is correct
7 Correct 357 ms 1011280 KB Output is correct
8 Correct 351 ms 1011024 KB Output is correct
9 Correct 350 ms 1011336 KB Output is correct
10 Correct 349 ms 1011032 KB Output is correct
11 Correct 389 ms 1012120 KB Output is correct
12 Incorrect 378 ms 1011588 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 1011184 KB Output is correct
2 Correct 353 ms 1011248 KB Output is correct
3 Correct 372 ms 1011036 KB Output is correct
4 Correct 356 ms 1011452 KB Output is correct
5 Correct 353 ms 1011024 KB Output is correct
6 Correct 368 ms 1011016 KB Output is correct
7 Correct 352 ms 1011028 KB Output is correct
8 Correct 364 ms 1011076 KB Output is correct
9 Correct 350 ms 1011108 KB Output is correct
10 Correct 353 ms 1011024 KB Output is correct
11 Correct 363 ms 1011024 KB Output is correct
12 Correct 363 ms 1011148 KB Output is correct
13 Correct 350 ms 1010980 KB Output is correct
14 Execution timed out 2566 ms 1048584 KB Time limit exceeded
15 Halted 0 ms 0 KB -