#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define ff first
#define ss second
const int N = 5e5 + 5;
int n, q;
int a[N];
struct Query {
int l, r, id;
bool operator < (const Query &o) const { return l > o.l; }
} Q[N];
int st[N], top;
int cnt;
pii p[N << 1];
void init() {
for (int i = 1; i <= n; ++i) {
while (top && a[st[top]] < a[i]) --top;
if (top) p[++cnt] = pii(st[top], i);
st[++top] = i;
}
top = 0;
for (int i = n; i; --i) {
while (top && a[st[top]] < a[i]) --top;
if (top) p[++cnt] = pii(i, st[top]);
st[++top] = i;
}
}
int seg[1 << 20], laz[1 << 20], ma1[1 << 20], ma2[1 << 20];
void build(int u, int l, int r) {
if (l == r) seg[u] = ma1[u] = a[l];
else {
int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
build(u1, l, m);
build(u2, m + 1, r);
seg[u] = ma1[u] = max(ma1[u1], ma1[u2]);
}
}
void update(int u, int l, int r, int a, int b, int v) {
if (a <= l && r <= b) {
if (ma2[u] < v) {
ma2[u] = laz[u] = v;
seg[u] = max(seg[u], v + ma1[u]);
return;
}
}
int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
if (laz[u]) {
if (laz[u] > ma2[u1]) {
ma2[u1] = laz[u1] = laz[u];
seg[u1] = max(seg[u1], laz[u] + ma1[u1]);
}
if (laz[u] > ma2[u2]) {
ma2[u2] = laz[u2] = laz[u];
seg[u2] = max(seg[u2], laz[u] + ma1[u2]);
}
laz[u] = 0;
}
if (a <= m) update(u1, l, m, a, b, v);
if (m < b) update(u2, m + 1, r, a, b, v);
seg[u] = max(seg[u1], seg[u2]);
}
void update(int l, int r, int v) {
if (l <= r) update(1, 1, n, l, r, v);
}
int get(int u, int l, int r, int a, int b) {
if (a <= l && r <= b) return seg[u];
if (b < l || r < a) return 0;
int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
if (laz[u]) {
if (laz[u] > ma2[u1]) {
ma2[u1] = laz[u1] = laz[u];
seg[u1] = max(seg[u1], laz[u] + ma1[u1]);
}
if (laz[u] > ma2[u2]) {
ma2[u2] = laz[u2] = laz[u];
seg[u2] = max(seg[u2], laz[u] + ma1[u2]);
}
laz[u] = 0;
}
return max(get(u1, l, m, a, b), get(u2, m + 1, r, a, b));
}
int ans[N];
void solve() {
init();
sort(Q + 1, Q + q + 1);
sort(p + 1, p + cnt + 1, [](const pii &a, const pii &b) { return a.ff > b.ff; });
build(1, 1, n);
for (int i = 1, j = 1; i <= q; ++i) {
while (j <= cnt && p[j].ff >= Q[i].l) {
update(p[j].ss * 2 - p[j].ff, n, a[p[j].ff] + a[p[j].ss]);
++j;
}
ans[Q[i].id] = get(1, 1, n, Q[i].l, Q[i].r);
}
}
int main() {
cin.tie(NULL)->sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
cin >> q;
for (int i = 1; i <= q; ++i)
cin >> Q[i].l >> Q[i].r, Q[i].id = i;
solve();
for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}
/** /\_/\
* (= ._.)
* / >0 \>1
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
852 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
852 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
80 ms |
18608 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
852 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
