#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Node {
int val, mi, ma;
Node():val(0), mi(0), ma(0) {}
Node(int _v, int _i, int _a) : val(_v), mi(_i), ma(_a) {}
};
struct SegTree {
vector<Node> seg;
int MAX;
SegTree(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
}
Node f(Node x, Node y) {
if(x.val>y.val) return x;
if(x.val<y.val) return y;
return Node(x.val, min(x.mi, y.mi), max(x.ma, y.ma));
}
void cons() {
for(int i = MAX/2-1;i>=1;i--) {
seg[i] = f(seg[2*i], seg[2*i+1]);
}
}
Node sum(int s, int e, int n, int ns, int ne) {
if(e<=ns||ne<=s) return Node();
if(s<=ns&&ne<=e) return seg[n];
int mid = ns + ne >> 1;
return f(sum(s, e, 2*n, ns, mid), sum(s, e, 2*n+1, mid, ne));
}
};
int A[500005];
int B[5005][5005];
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
int i, j;
for(i=0;i<N;i++) cin >> A[i];
SegTree tree(N);
int MAX = tree.MAX;
for(i=0;i<N;i++) tree.seg[i+MAX/2] = Node(A[i],i,i);
tree.cons();
/*for(int l = 0; l < N; l++) {
for(int r = l + 2; r < N; r++) {
B[l][r] = A[l]+A[r]+tree.sum(l+1, (l+r)/2+1, 1, 0, MAX/2);
}
}*/
/*for(int len = 3; len <= N-1; len++) {
for(i=0;i+len<=N-1;i++) {
B[i][i+len] = max(B[i][i+len], B[i+1][i+len]);
B[i][i+len] = max(B[i][i+len], B[i][i+len-1]);
}
}*/
int Q;
cin >> Q;
while(Q--) {
int l, r;
cin >> l >> r;
l--, r--;
int ans = 0;
for(i=l;i<=r-2;i++) {
Node v = tree.sum(i+2, r+1, 1, 0, MAX/2);
int id = v.ma;
v = tree.sum(i+1, (i+id)/2+1, 1, 0, MAX/2);
ans = max(ans, A[i] + A[id] + v.val);
v = tree.sum(i+1, (i+r)/2+1, 1, 0, MAX/2);
id = v.mi;
v = tree.sum(2*id - i, r+1, 1, 0, MAX/2);
ans = max(ans, A[i] + A[id] + v.val);
}
cout << ans << '\n';
}
}
Compilation message
jumps.cpp: In member function 'Node SegTree::sum(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | int mid = ns + ne >> 1;
| ~~~^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:43:12: warning: unused variable 'j' [-Wunused-variable]
43 | int i, j;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
3 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
3 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
202 ms |
14156 KB |
Output is correct |
2 |
Correct |
191 ms |
14164 KB |
Output is correct |
3 |
Correct |
173 ms |
14164 KB |
Output is correct |
4 |
Correct |
203 ms |
14200 KB |
Output is correct |
5 |
Correct |
204 ms |
14136 KB |
Output is correct |
6 |
Correct |
207 ms |
14152 KB |
Output is correct |
7 |
Correct |
196 ms |
14164 KB |
Output is correct |
8 |
Correct |
197 ms |
14128 KB |
Output is correct |
9 |
Correct |
214 ms |
14164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
3 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |