#include<bits/stdc++.h>
using namespace std;
typedef pair<int , int> ipair;
const int N = 5e5 + 5;
int n , q , a[N] , ans[N];
vector<ipair> Q[N];
vector<int> e[N];
void R(){
stack<int> s;
for(int i = 1; i <= n; ++i){
while(!s.empty() && a[i] >= a[s.top()]) e[s.top()].emplace_back(i) , s.pop();
if(!s.empty()) e[s.top()].emplace_back(i);
s.push(i);
}
}
struct Node{
int mx , f , a;
}T[1<<20];
Node operator+(const Node &A , const Node &B){
Node ret;
ret.mx = max({A.mx , A.f + B.a , B.mx});
ret.a = max(A.a , B.a);
ret.f = max(A.f , B.f);
return ret;
}
void B(int l = 1 , int r= n , int pos = 1){
if(l == r){
T[pos].a = a[l]; return;
}
int mid = (l + r)>>1;
B(l , mid , pos * 2 ); B(mid + 1 ,r , pos * 2 + 1);
T[pos].a = max(T[pos* 2].a , T[pos * 2 + 1].a);
}
void upd(int i , int x , int l = 1 , int r = n , int pos = 1){
if(i < l || i > r)return;
if(l == r){
T[pos].f = max(T[pos].f , x);
T[pos].mx = T[pos].f + T[pos].a;
return;
}
int mid = (l + r)>>1;
if(i <= mid) upd(i ,x , l ,mid, pos * 2);
else upd(i ,x , mid +1 , r, pos * 2 + 1);
T[pos] = T[pos * 2 ] + T[pos * 2 + 1];
}
Node get(int L ,int R , int l = 1 , int r= n , int pos = 1){
if(r < L || R < l)return {0 ,0 ,0};
if(L <= l && r <= R) return T[pos];
int mid = (l + r)>>1;
return get(L , R , l , mid , pos * 2 ) + get(L , R ,mid + 1 , r , pos * 2 + 1);
}
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for(int i =1; i <= n; ++i)cin >> a[i];
cin >> q;
for(int i = 0; i < q; ++i){
int l , r; cin >> l >> r;
Q[l].emplace_back(r , i);
}
R();
B();
//for(auto x : e)cout << x.first << " " << x.second << endl;
for(int l = n; l; --l){
for(int x : e[l])if(2 * x - l <= n) upd(2 * x - l , a[l] + a[x]);
for(auto X : Q[l]){
int i = X.second , r = X.first;
ans[i] = get(l , r).mx;
}
}
for(int i= 0; i < q; ++i)cout << ans[i] << " ";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Correct |
16 ms |
23788 KB |
Output is correct |
3 |
Correct |
16 ms |
23788 KB |
Output is correct |
4 |
Correct |
16 ms |
23788 KB |
Output is correct |
5 |
Correct |
17 ms |
23916 KB |
Output is correct |
6 |
Correct |
16 ms |
23788 KB |
Output is correct |
7 |
Correct |
15 ms |
23788 KB |
Output is correct |
8 |
Correct |
15 ms |
23788 KB |
Output is correct |
9 |
Correct |
16 ms |
23788 KB |
Output is correct |
10 |
Correct |
15 ms |
23788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Correct |
16 ms |
23788 KB |
Output is correct |
3 |
Correct |
16 ms |
23788 KB |
Output is correct |
4 |
Correct |
16 ms |
23788 KB |
Output is correct |
5 |
Correct |
17 ms |
23916 KB |
Output is correct |
6 |
Correct |
16 ms |
23788 KB |
Output is correct |
7 |
Correct |
15 ms |
23788 KB |
Output is correct |
8 |
Correct |
15 ms |
23788 KB |
Output is correct |
9 |
Correct |
16 ms |
23788 KB |
Output is correct |
10 |
Correct |
15 ms |
23788 KB |
Output is correct |
11 |
Correct |
446 ms |
38052 KB |
Output is correct |
12 |
Correct |
457 ms |
37876 KB |
Output is correct |
13 |
Correct |
458 ms |
37980 KB |
Output is correct |
14 |
Correct |
457 ms |
37996 KB |
Output is correct |
15 |
Correct |
450 ms |
37972 KB |
Output is correct |
16 |
Correct |
450 ms |
37356 KB |
Output is correct |
17 |
Correct |
459 ms |
37484 KB |
Output is correct |
18 |
Correct |
460 ms |
37356 KB |
Output is correct |
19 |
Correct |
454 ms |
37824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
184 ms |
37228 KB |
Output is correct |
2 |
Correct |
112 ms |
37100 KB |
Output is correct |
3 |
Correct |
113 ms |
37996 KB |
Output is correct |
4 |
Correct |
184 ms |
37228 KB |
Output is correct |
5 |
Correct |
183 ms |
37228 KB |
Output is correct |
6 |
Correct |
181 ms |
37356 KB |
Output is correct |
7 |
Correct |
181 ms |
37228 KB |
Output is correct |
8 |
Correct |
179 ms |
37228 KB |
Output is correct |
9 |
Correct |
183 ms |
37356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Correct |
16 ms |
23788 KB |
Output is correct |
3 |
Correct |
16 ms |
23788 KB |
Output is correct |
4 |
Correct |
16 ms |
23788 KB |
Output is correct |
5 |
Correct |
17 ms |
23916 KB |
Output is correct |
6 |
Correct |
16 ms |
23788 KB |
Output is correct |
7 |
Correct |
15 ms |
23788 KB |
Output is correct |
8 |
Correct |
15 ms |
23788 KB |
Output is correct |
9 |
Correct |
16 ms |
23788 KB |
Output is correct |
10 |
Correct |
15 ms |
23788 KB |
Output is correct |
11 |
Correct |
446 ms |
38052 KB |
Output is correct |
12 |
Correct |
457 ms |
37876 KB |
Output is correct |
13 |
Correct |
458 ms |
37980 KB |
Output is correct |
14 |
Correct |
457 ms |
37996 KB |
Output is correct |
15 |
Correct |
450 ms |
37972 KB |
Output is correct |
16 |
Correct |
450 ms |
37356 KB |
Output is correct |
17 |
Correct |
459 ms |
37484 KB |
Output is correct |
18 |
Correct |
460 ms |
37356 KB |
Output is correct |
19 |
Correct |
454 ms |
37824 KB |
Output is correct |
20 |
Correct |
184 ms |
37228 KB |
Output is correct |
21 |
Correct |
112 ms |
37100 KB |
Output is correct |
22 |
Correct |
113 ms |
37996 KB |
Output is correct |
23 |
Correct |
184 ms |
37228 KB |
Output is correct |
24 |
Correct |
183 ms |
37228 KB |
Output is correct |
25 |
Correct |
181 ms |
37356 KB |
Output is correct |
26 |
Correct |
181 ms |
37228 KB |
Output is correct |
27 |
Correct |
179 ms |
37228 KB |
Output is correct |
28 |
Correct |
183 ms |
37356 KB |
Output is correct |
29 |
Correct |
1314 ms |
71220 KB |
Output is correct |
30 |
Correct |
1144 ms |
81600 KB |
Output is correct |
31 |
Correct |
1152 ms |
83588 KB |
Output is correct |
32 |
Correct |
1344 ms |
82412 KB |
Output is correct |
33 |
Correct |
1324 ms |
82284 KB |
Output is correct |
34 |
Correct |
1333 ms |
79980 KB |
Output is correct |
35 |
Correct |
1308 ms |
79852 KB |
Output is correct |
36 |
Correct |
1300 ms |
79848 KB |
Output is correct |
37 |
Correct |
1302 ms |
81004 KB |
Output is correct |
38 |
Correct |
1004 ms |
88008 KB |
Output is correct |
39 |
Correct |
998 ms |
87916 KB |
Output is correct |
40 |
Correct |
988 ms |
84588 KB |
Output is correct |
41 |
Correct |
971 ms |
84136 KB |
Output is correct |
42 |
Correct |
984 ms |
84204 KB |
Output is correct |
43 |
Correct |
981 ms |
85996 KB |
Output is correct |
44 |
Correct |
1052 ms |
87276 KB |
Output is correct |
45 |
Correct |
1045 ms |
87404 KB |
Output is correct |
46 |
Correct |
1025 ms |
84460 KB |
Output is correct |
47 |
Correct |
1032 ms |
83820 KB |
Output is correct |
48 |
Correct |
1032 ms |
83820 KB |
Output is correct |
49 |
Correct |
1035 ms |
85852 KB |
Output is correct |
50 |
Correct |
1122 ms |
85228 KB |
Output is correct |
51 |
Correct |
1125 ms |
85356 KB |
Output is correct |
52 |
Correct |
1117 ms |
83052 KB |
Output is correct |
53 |
Correct |
1110 ms |
82540 KB |
Output is correct |
54 |
Correct |
1107 ms |
82412 KB |
Output is correct |
55 |
Correct |
1128 ms |
84012 KB |
Output is correct |