oj.uz

답안 #926825

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926825 2024-02-13T20:44:53 Z OAleksa Team Contest (JOI22_team) C++14
0 / 100
 2000 ms 1048580 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, 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -