#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pi pair<int, int>
#define vi vector<int>
#define pb push_back
//max1 = A + B, max2 = C, max3 = A + B + C
struct node {
int max1, max2, max3;
};
constexpr int base = (1 << 19);
constexpr int LIM = 5e5;
node INF;
node tri[2 * base];
int tab[LIM + 10];
vi can[LIM + 10];
vector<pi> zap[LIM + 10];
int ans[LIM + 10];
int lasy[2 * base];
node merge(node a, node b) {
node res;
res.max1 = max(a.max1, b.max1);
res.max2 = max(a.max2, b.max2);
res.max3 = max({a.max3, b.max3, a.max1 + b.max2});
return res;
}
void spl(int v) {
tri[2 * v].max1 = max(tri[2 * v].max1, lasy[v]);
tri[2 * v].max3 = max(tri[2 * v].max3, lasy[v] + tri[2 * v].max2);
tri[2 * v + 1].max1 = max(tri[2 * v + 1].max1, lasy[v]);
tri[2 * v + 1].max3 = max(tri[2 * v + 1].max3, lasy[v] + tri[2 * v + 1].max2);
}
void upd(int v, int l, int r, int a, int b, int x) {
if(l > b || r < a) {
return;
}
if(a <= l && r <= b) {
tri[v].max1 = max(tri[v].max1, x);
tri[v].max3 = max(tri[v].max3, x + tri[v].max2);
lasy[v] = max(lasy[v], x);
return;
}
spl(v);
int mid = (l + r) / 2;
upd(2 * v, l, mid, a, b, x);
upd(2 * v + 1, mid + 1, r, a, b, x);
tri[v] = merge(tri[2 * v], tri[2 * v + 1]);
}
node res;
void query(int v, int l, int r, int a, int b) {
if(l > b || r < a) {
return;
}
if(a <= l && r <= b) {
res = merge(res, tri[v]);
return;
}
spl(v);
int mid = (l + r) / 2;
query(2 * v, l, mid, a, b);
query(2 * v + 1, mid + 1, r, a, b);
tri[v] = merge(tri[2 * v], tri[2 * v + 1]);
}
int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
INF.max1 = -1e9, INF.max2 = -1e9, INF.max3 = -1e9;
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> tab[i];
tri[i + base - 1] = INF;
tri[i + base - 1].max2 = tab[i];
}
for(int i = base - 1; i >= 1; i--) {
tri[i] = merge(tri[2 * i], tri[2 * i + 1]);
}
stack<int>s;
for(int i = 1; i <= n; i++) {
while(!s.empty() && tab[s.top()] <= tab[i]) {
can[s.top()].pb(i);
s.pop();
}
if(!s.empty()) {
can[s.top()].pb(i);
}
s.push(i);
}
int t;
cin >> t;
for(int i = 1; i <= t; i++) {
int l, r;
cin >> l >> r;
zap[l].pb({r, i});
}
for(int i = n; i >= 1; i--) {
for(auto x : can[i]) {
upd(1, 1, base, 2 * x - i, n, tab[i] + tab[x]);
}
for(auto x : zap[i]) {
res = INF;
query(1, 1, base, i, x.st);
ans[x.nd] = res.max3;
}
}
for(int i = 1; i <= t; i++) {
cout << ans[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
29956 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
29908 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
29956 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
29908 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
364 ms |
42812 KB |
Output is correct |
| 2 |
Correct |
219 ms |
42692 KB |
Output is correct |
| 3 |
Correct |
240 ms |
43556 KB |
Output is correct |
| 4 |
Correct |
369 ms |
42896 KB |
Output is correct |
| 5 |
Correct |
389 ms |
42808 KB |
Output is correct |
| 6 |
Correct |
336 ms |
42336 KB |
Output is correct |
| 7 |
Correct |
396 ms |
42136 KB |
Output is correct |
| 8 |
Correct |
350 ms |
42156 KB |
Output is correct |
| 9 |
Correct |
364 ms |
42456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
29956 KB |
Output is correct |
| 2 |
Incorrect |
26 ms |
29908 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
