This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
const int INF = 1e9;
const int mod = 998244353;
const int N = 200005;
int sp[N][20];
int get(int l, int r){
int lg = __lg(r - l + 1);
return max(sp[l][lg], sp[r - (1ll << lg) + 1][lg]);
}
void solve(){
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = 0; i < n; i++){
sp[i][0] = a[i];
}
for(int i = 1; i < 20; i++){
for(int j = 0; j < n; j++){
sp[j][i] = max(sp[j][i - 1], sp[min(n - 1, j + (1ll << (i - 1)))][i - 1]);
}
}
int q;
cin >> q;
while(q--){
int l, r;
cin >> l >> r;
l--;
r--;
int mx = get(l, r), pos = l;
for(int i = r; i >= l; i--){
if(a[i] == mx){
pos = i;
break;
}
}
int ans = 0;
for(int i = l; i < pos; i++){
if(i != l) ans = max(ans, a[pos] + a[i] + get(max(l, i - (pos - i)), i - 1));
if(pos + (pos - i) <= r) ans = max(ans, a[pos] + a[i] + get(pos + (pos - i), r));
}
for(int i = pos + 1; i < r; i++){
if(i + (i - pos) <= r) ans = max(ans, a[pos] + a[i] + get(i + (i - pos), r));
else break;
}
for(int i = l; i <= r; i++){
if(a[i] == mx){
pos = i;
break;
}
}
for(int i = l; i < pos; i++){
if(i != l) ans = max(ans, a[pos] + a[i] + get(max(l, i - (pos - i)), i - 1));
if(pos + (pos - i) <= r) ans = max(ans, a[pos] + a[i] + get(pos + (pos - i), r));
}
for(int i = pos + 1; i < r; i++){
if(i + (i - pos) <= r) ans = max(ans, a[pos] + a[i] + get(i + (i - pos), r));
else break;
}
cout << ans << '\n';
}
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while(tt--){
solve();
}
}
Compilation message (stderr)
jumps.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
79 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |