#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 21, kaf = 1 << 20, inf = 1e15;
struct segment {
int seg[1 << maxn], mx[1 << maxn], lazy[1 << maxn];
segment (){
for (int i = 0; i < (1 << maxn); i++)
seg[i] = lazy[i] = 0;
}
void build (int i){
if ((i << 1) >= (1 << maxn)) return;
build(i << 1), build((i << 1) ^ 1);
mx[i] = max(mx[i << 1], mx[(i << 1) ^ 1]);
}
void shift (int i){
if ((i << 1) >= (1 << maxn)) return;
lazy[i << 1] = max(lazy[i << 1], lazy[i]);
lazy[(i << 1) ^ 1] = max(lazy[(i << 1) ^ 1], lazy[i]);
seg[i << 1] = max(seg[i << 1], mx[i << 1] + lazy[i << 1]);
seg[(i << 1) ^ 1] = max(seg[(i << 1) ^ 1], mx[(i << 1) ^ 1] + lazy[(i << 1) ^ 1]);
lazy[i] = 0;
}
void update (int i, int L, int R, int l, int r, int x){
if (L > r || R < l) return;
if (L >= l && R <= r){
lazy[i] = max(lazy[i], x);
seg[i] = max(seg[i], mx[i] + lazy[i]);
return;
}
shift(i);
int mid = (R + L) >> 1;
update(i << 1, L, mid, l, r, x);
update((i << 1) ^ 1, mid + 1, R, l, r, x);
seg[i] = max(seg[i << 1], seg[(i << 1) ^ 1]);
}
int get (int i, int L, int R, int l, int r){
if (L > r || R < l) return 0;
if (L >= l && R <= r) return seg[i];
shift(i);
int mid = (R + L) >> 1;
return max(get(i << 1, L, mid, l, r), get((i << 1) ^ 1, mid + 1, R, l, r));
}
};
segment seg;
int n, q;
int32_t main (){
ios_base::sync_with_stdio(0);
cin >> n;
vector <int> a(n), p[2 * n];
vector <pair <int, int>> que[n];
for (int i = 0; i < n; i++)
cin >> a[i], seg.mx[kaf + i] = a[i];
seg.build(1);
cin >> q;
vector <int> ans(q);
for (int l, r, i = 0; i < q; i++)
cin >> l >> r,
que[--l].push_back({--r, i});
stack <int> stc;
for (int i = 0; i < n; i++){
while (stc.size() && a[i] < a[stc.top()])
p[stc.top()].push_back(i),
stc.pop();
if (stc.size()) p[stc.top()].push_back(i);
stc.push(i);
}
for (int i = n - 1; ~i; i--){
for (auto r : p[i])
if (2 * r - i < n)
seg.update(1, 0, kaf - 1, 2 * r - i, n - 1, a[i] + a[r]);
for (auto [r, ind] : que[i])
ans[ind] = seg.get(1, 0, kaf - 1, i, r);
}
for (int i : ans) cout << i << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
43344 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
43344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
43344 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
43344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
211 ms |
70312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
43344 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
43344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
