#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
int N; i64 a[500005], sparse[500005][22];
int getMax(int L, int R) {
int j = log2(R - L + 1);
return max(sparse[L][j], sparse[R - (1 << j) + 1][j]);
}
// struct Tree{
// int n;
// vector<int64_t>lazy;
// vector<int64_t>st;
// Tree(int _n, int64_t _v): n(_n), st(_n * 4, _v), lazy(_n * 4, _v){};
// void push(int id){
// int64_t add = lazy[id];
// lazy[id * 2] += add, st[id * 2] += add;
// lazy[id * 2 + 1] += add, st[id * 2 + 1] += add;
// lazy[id] = 0;
// }
// void update(int id, int l, int r, int u, int v, int64_t val){
// if (v < l || u > r) return;
// if (u <= l && r <= v) {
// st[id] = val;
// lazy[id] = val;
// return;
// }
// // push(id);
// int mid = (l + r)/2;
// update(id * 2, l, mid, u, v, val);
// update(id * 2 + 1, mid + 1, r, u, v, val);
// st[id] = max(st[id * 2], st[id * 2 + 1]);
// }
// int find(int id, int l, int r, int u, int v, int x){
// if (v < l || u > r) return N + 1;
// if (st[id] <= x) return N + 1;
// if (l == r) return l;
// // push(id);
// int mid = (l + r)/2;
// int lf = find(id * 2, l, mid, u, v, x);
// if (lf != N + 1) return lf;
// return find(id * 2 + 1, mid + 1, r, u, v, x);
// }
// int get(int id, int l, int r, int u, int v) {
// if (v < l || u > r) return 0;
// if (u <= l && r <= v) return st[id];
// int mid = (l + r)/2;
// return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
// }
// };
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i ++) cin >> a[i];
for (int i = N; i >= 1; i --) {
sparse[i][0] = a[i];
for (int j = 1; j <= 20; j ++) {
if (i + (1 << (j - 1)) <= N) {
sparse[i][j] = max(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
}
}
}
set<pair<int, int>> s;
int Q; cin >> Q; while (Q --) {
int L, R; cin >> L >> R;
for (int i = L; i <= R; i ++) {
s.insert(mp(a[i], i));
if (s.size() > 3) s.erase(s.begin());
}
vector<int> ids;
for (auto [x, id] : s) ids.pb(id);
sort(all(ids));
i64 ans = 0;
for (int i = 0; i < (int)ids.size() - 1; i ++) {
int lf = ids[i], rg = ids[i + 1];
int gap = rg - lf;
if (lf > 1) {
ans = max(ans, getMax(lf - gap, lf - 1) + a[lf] + a[rg]);
} if (rg + gap <= N) {
ans = max(ans, a[lf] + a[rg] + getMax(rg + gap, N));
} if (gap > 1) {
ans = max(ans, a[lf] + getMax(lf + 1, (lf + rg)/2) + a[rg]);
}
}
cout << ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
37972 KB |
Output is correct |
| 2 |
Correct |
41 ms |
37968 KB |
Output is correct |
| 3 |
Correct |
40 ms |
38032 KB |
Output is correct |
| 4 |
Incorrect |
43 ms |
37972 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
