#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = a ; i <= b ; ++i)
#define X first
#define Y second
#define pb push_back
#define ll long long
#define lch i << 1
#define rch i << 1 | 1
#define Unit Node(-2e9,-2e9,-3e9)
const int N = 5e5 + 1;
typedef pair<int,int> ii;
struct Node {
ll L, R, S;
Node(ll l = 0,ll r = 0,ll s = 0) : L(l), R(r), S(s) {}
} tr[N << 2];
Node Spare;
Node operator + (const Node &a,const Node &b) {
ll x = max(a.L,b.L);
ll y = max(a.R,b.R);
ll z = max(a.S,b.S);
return Node(x,y,max(z,a.L + b.R));
}
void upd(int i,int l,int r,int p,int v,int t) {
if (l > p) return;
if (r < p) return;
if (l == r) {
if (t) tr[i].R = max(tr[i].R,(ll)v);
else tr[i].L = max(tr[i].L,(ll)v);
tr[i].S = tr[i].L + tr[i].R;
return;
}
int m = (l + r) / 2;
upd(lch,l,m,p,v,t); ++m;
upd(rch,m,r,p,v,t);
tr[i] = tr[lch] + tr[rch];
}
void get(int i,int l,int r,int L,int R) {
if (l > R) return;
if (L > r) return;
if (L <= l && r <= R) {
Spare = Spare + tr[i];
return;
}
int m = (l + r) / 2;
get(lch,l,m,L,R); ++m;
get(rch,m,r,L,R);
}
vector<ii> Que[N];
vector<ii> Seg[N];
int a[N];
int t[N];
int tot = 0;
ll ans[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
fill(tr + 1,tr + 4 * n,Unit);
auto add = [&](int x,int y) {
if (y + y <= n + x)
Seg[x].pb(ii(y + y - x,a[x] + a[y]));
};
auto ask = [&](int l,int r) {
Spare = Unit;
get(1,1,n,l,r);
return Spare.S;
};
FOR(i,1,n) {
cin >> a[i];
for(; tot && a[t[tot]] < a[i] ; --tot)
add(t[tot],i);
if (tot)
add(t[tot],i);
t[++tot] = i;
}
int q; cin >> q;
FOR(i,1,q) {
int l; cin >> l;
int r; cin >> r;
Que[l].push_back(ii(r,i));
}
for(int i = n ; i >= 1 ; --i) {
upd(1,1,n,i,a[i],1);
for(ii e : Seg[i])
upd(1,1,n,e.X,e.Y,0);
for(ii e : Que[i])
ans[e.Y] = ask(i,e.X);
}
FOR(i,1,q) cout << ans[i] << "\n";
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
70840 KB |
Output is correct |
2 |
Correct |
66 ms |
70764 KB |
Output is correct |
3 |
Correct |
65 ms |
70776 KB |
Output is correct |
4 |
Correct |
66 ms |
70776 KB |
Output is correct |
5 |
Correct |
66 ms |
70776 KB |
Output is correct |
6 |
Correct |
65 ms |
70772 KB |
Output is correct |
7 |
Correct |
65 ms |
70776 KB |
Output is correct |
8 |
Correct |
66 ms |
70776 KB |
Output is correct |
9 |
Correct |
67 ms |
70776 KB |
Output is correct |
10 |
Correct |
68 ms |
70780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
70840 KB |
Output is correct |
2 |
Correct |
66 ms |
70764 KB |
Output is correct |
3 |
Correct |
65 ms |
70776 KB |
Output is correct |
4 |
Correct |
66 ms |
70776 KB |
Output is correct |
5 |
Correct |
66 ms |
70776 KB |
Output is correct |
6 |
Correct |
65 ms |
70772 KB |
Output is correct |
7 |
Correct |
65 ms |
70776 KB |
Output is correct |
8 |
Correct |
66 ms |
70776 KB |
Output is correct |
9 |
Correct |
67 ms |
70776 KB |
Output is correct |
10 |
Correct |
68 ms |
70780 KB |
Output is correct |
11 |
Correct |
456 ms |
86876 KB |
Output is correct |
12 |
Correct |
434 ms |
91032 KB |
Output is correct |
13 |
Correct |
417 ms |
90976 KB |
Output is correct |
14 |
Correct |
426 ms |
91196 KB |
Output is correct |
15 |
Correct |
416 ms |
91336 KB |
Output is correct |
16 |
Correct |
421 ms |
90360 KB |
Output is correct |
17 |
Correct |
430 ms |
90428 KB |
Output is correct |
18 |
Correct |
414 ms |
90376 KB |
Output is correct |
19 |
Correct |
431 ms |
90928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
375 ms |
80852 KB |
Output is correct |
2 |
Correct |
270 ms |
79608 KB |
Output is correct |
3 |
Correct |
272 ms |
80504 KB |
Output is correct |
4 |
Correct |
376 ms |
80864 KB |
Output is correct |
5 |
Correct |
377 ms |
80740 KB |
Output is correct |
6 |
Correct |
370 ms |
80204 KB |
Output is correct |
7 |
Correct |
395 ms |
80076 KB |
Output is correct |
8 |
Correct |
366 ms |
79972 KB |
Output is correct |
9 |
Correct |
398 ms |
80416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
70840 KB |
Output is correct |
2 |
Correct |
66 ms |
70764 KB |
Output is correct |
3 |
Correct |
65 ms |
70776 KB |
Output is correct |
4 |
Correct |
66 ms |
70776 KB |
Output is correct |
5 |
Correct |
66 ms |
70776 KB |
Output is correct |
6 |
Correct |
65 ms |
70772 KB |
Output is correct |
7 |
Correct |
65 ms |
70776 KB |
Output is correct |
8 |
Correct |
66 ms |
70776 KB |
Output is correct |
9 |
Correct |
67 ms |
70776 KB |
Output is correct |
10 |
Correct |
68 ms |
70780 KB |
Output is correct |
11 |
Correct |
456 ms |
86876 KB |
Output is correct |
12 |
Correct |
434 ms |
91032 KB |
Output is correct |
13 |
Correct |
417 ms |
90976 KB |
Output is correct |
14 |
Correct |
426 ms |
91196 KB |
Output is correct |
15 |
Correct |
416 ms |
91336 KB |
Output is correct |
16 |
Correct |
421 ms |
90360 KB |
Output is correct |
17 |
Correct |
430 ms |
90428 KB |
Output is correct |
18 |
Correct |
414 ms |
90376 KB |
Output is correct |
19 |
Correct |
431 ms |
90928 KB |
Output is correct |
20 |
Correct |
375 ms |
80852 KB |
Output is correct |
21 |
Correct |
270 ms |
79608 KB |
Output is correct |
22 |
Correct |
272 ms |
80504 KB |
Output is correct |
23 |
Correct |
376 ms |
80864 KB |
Output is correct |
24 |
Correct |
377 ms |
80740 KB |
Output is correct |
25 |
Correct |
370 ms |
80204 KB |
Output is correct |
26 |
Correct |
395 ms |
80076 KB |
Output is correct |
27 |
Correct |
366 ms |
79972 KB |
Output is correct |
28 |
Correct |
398 ms |
80416 KB |
Output is correct |
29 |
Correct |
1741 ms |
121320 KB |
Output is correct |
30 |
Correct |
1433 ms |
118240 KB |
Output is correct |
31 |
Correct |
1418 ms |
120104 KB |
Output is correct |
32 |
Correct |
1709 ms |
121216 KB |
Output is correct |
33 |
Correct |
1705 ms |
121412 KB |
Output is correct |
34 |
Correct |
1692 ms |
119056 KB |
Output is correct |
35 |
Correct |
1668 ms |
118476 KB |
Output is correct |
36 |
Correct |
1681 ms |
118676 KB |
Output is correct |
37 |
Correct |
1715 ms |
120180 KB |
Output is correct |
38 |
Correct |
1264 ms |
126852 KB |
Output is correct |
39 |
Correct |
1267 ms |
126968 KB |
Output is correct |
40 |
Correct |
1256 ms |
123480 KB |
Output is correct |
41 |
Correct |
1236 ms |
123192 KB |
Output is correct |
42 |
Correct |
1240 ms |
123256 KB |
Output is correct |
43 |
Correct |
1248 ms |
124964 KB |
Output is correct |
44 |
Correct |
1365 ms |
126208 KB |
Output is correct |
45 |
Correct |
1684 ms |
126424 KB |
Output is correct |
46 |
Correct |
1328 ms |
123040 KB |
Output is correct |
47 |
Correct |
1324 ms |
122860 KB |
Output is correct |
48 |
Correct |
1315 ms |
122848 KB |
Output is correct |
49 |
Correct |
1340 ms |
125064 KB |
Output is correct |
50 |
Correct |
1494 ms |
124416 KB |
Output is correct |
51 |
Correct |
1471 ms |
124628 KB |
Output is correct |
52 |
Correct |
1606 ms |
122088 KB |
Output is correct |
53 |
Correct |
1451 ms |
121592 KB |
Output is correct |
54 |
Correct |
1438 ms |
121624 KB |
Output is correct |
55 |
Correct |
1472 ms |
123356 KB |
Output is correct |