oj.uz

Submission #859253

# Submission time Handle Problem Language Result Execution time Memory
859253 2023-10-10T02:22:57 Z mgl_diamond Triple Jump (JOI19_jumps) C++17
27 / 100
 285 ms 24400 KB 
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;


#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)

const int N = 5e5+5;
const int BIG = 2e9;
int n, q, a[N];
int sgt[N * 4], pos[N * 4];

int comb(int i, int j) {
	return a[i] >= a[j] ? i : j;
}

void build(int id, int lb, int rb) {
	if (lb ^ rb) {
		int mb = (lb + rb) >> 1;
		build(id*2, lb, mb);
		build(id*2+1, mb+1, rb);
		sgt[id] = max(sgt[id*2], sgt[id*2+1]);
		pos[id] = comb(pos[id*2], pos[id*2+1]);
	}
	else {
		sgt[id] = a[lb];
		pos[id] = lb;
	}
}

int query(int id, int lb, int rb, int l, int r) {
	if (l <= lb && rb <= r) return sgt[id];
	if (rb < l || lb > r) return -BIG;
	int mb = (lb + rb) >> 1;
	return max(query(id*2, lb, mb, l, r), query(id*2+1, mb+1, rb, l, r));
}

int findpos(int id, int lb, int rb, int l, int r) {
	if (l <= lb && rb <= r) return pos[id];
	if (rb < l || lb > r) return 0;
	int mb = (lb + rb) >> 1;
	return comb(findpos(id*2, lb, mb, l, r), findpos(id*2+1, mb+1, rb, l, r));
}

int solve(int l, int r) {
	if ((r-l+1) < 3) return 0;

	int pos_max = findpos(1, 1, n, l+1, r-1);

	int ans = max(solve(l, pos_max), solve(pos_max, r));
	
	if (r - pos_max < pos_max - l) {
		for(int d = 1; d <= r - pos_max; ++d) {
			int k = pos_max+d;
			ans = max(ans, a[k] + a[pos_max] + query(1, 1, n, pos_max-d, pos_max-1));
		}
	}
	else {
		for(int d = 1; d <= pos_max - l; ++d) {
			int k = pos_max-d;
			ans = max(ans, a[k] + a[pos_max] + query(1, 1, n, pos_max+d, r));
		}
	}

	// cout << l << " " << r << " " << ans << "\n";
	return ans;
}

int main() {
	cin >> n;
	foru(i, 1, n) cin >> a[i];
	build(1, 1, n);
	cin >> q;
	foru(i, 1, q) {
		int l, r;
		cin >> l >> r;
		cout << solve(l, r) << "\n";
	}
	// cout << solve(1, n);
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 2 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 2 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 8808 KB Output is correct
2 Correct 132 ms 24400 KB Output is correct
3 Correct 128 ms 24248 KB Output is correct
4 Correct 271 ms 8804 KB Output is correct
5 Correct 285 ms 8784 KB Output is correct
6 Correct 243 ms 8808 KB Output is correct
7 Correct 238 ms 8888 KB Output is correct
8 Correct 233 ms 8804 KB Output is correct
9 Correct 244 ms 8804 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 2 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -