oj.uz

Submission #489442

# Submission time Handle Problem Language Result Execution time Memory
489442 2021-11-23T02:08:07 Z 8e7 Triple Jump (JOI19_jumps) C++17
27 / 100
 72 ms 19172 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 500005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int a[maxn], pref[maxn], suf[maxn], sp[19][maxn];
pii ma[maxn];
int getma(int l, int r) {
	int len = __lg(r - l + 1);
	return max(sp[len][l], sp[len][r - (1<<len)+1]); 
}
int main() {
	io
	int n, q;
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i], ma[i] = {a[i], i}, sp[0][i] = a[i];
	for (int i = 1;i <= n;i++) pref[i] = max(a[i], pref[i-1]);
	for (int i = n;i >= 1;i--) suf[i] = max(a[i], suf[i+1]);
	sort(ma + 1, ma + n + 1, [&](pii x, pii y){return x.ff > y.ff;});
	for (int i = 1;i < 19;i++) {
		for (int j = 1;j <= n - (1<<i)+1;j++) {
			sp[i][j] = max(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
		}
	}
	cin >> q;
	if (q > 1) {
		return 0;
	}
	for (int i = 0;i < q;i++) {
		int l, r;
		cin >> l >> r;
		int ans = 0;
		for (int j = 1;j <= min(n, 20);j++) {
			int id = ma[j].ss, val = ma[j].ff;
			for (int k = 1;k < id;k++) {
				if (2*id - k <= n) ans = max(ans, val + a[k] + suf[2*id-k]);	
				if (k>1) ans = max(ans, val + a[k] + getma(max(1, 2*k-id), k - 1)); 
			}
			for (int k = id + 1;k < n;k++) {
				if (2*k - id <= n) ans = max(ans, val + a[k] + suf[2*k-id]);
			}
		}
		cout << ans << endl;
	}
}
/*
5
5 2 1 5 3
1
1 5


5
5 4 4 5 4
1
1 5

15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
12
1 15
3 12
11 14
1 13
5 9
4 6
6 14
2 5
4 15
1 7
1 10
8 13
*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 1 ms 332 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 56 ms 17316 KB Output is correct
2 Correct 49 ms 17420 KB Output is correct
3 Correct 33 ms 17328 KB Output is correct
4 Correct 56 ms 17348 KB Output is correct
5 Correct 58 ms 19172 KB Output is correct
6 Correct 63 ms 18412 KB Output is correct
7 Correct 72 ms 18320 KB Output is correct
8 Correct 54 ms 18408 KB Output is correct
9 Correct 46 ms 18740 KB Output is correct

Subtask #4
0 / 54.0

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