//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
llo n;
llo it[500001];
vector<pair<llo,llo>> tt[500001];
llo tree[4*500001];
llo tree2[4*500001];
llo lazy[4*500001];
llo ans[500001];
void build(llo no,llo l,llo r){
if(l==r){
tree2[no]=it[l];
}
else{
llo mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
}
}
void push(llo no,llo l,llo r){
tree[no]=max(tree[no],tree2[no]+lazy[no]);
if(l<r){
lazy[no*2+1]=max(lazy[no*2+1],lazy[no]);
lazy[no*2+2]=max(lazy[no*2+2],lazy[no]);
}
lazy[no]=0;
}
void update(llo no,llo l,llo r,llo aa,llo bb,llo val){
push(no,l,r);
if(r<aa or l>bb){
return;
}
if(aa<=l and r<=bb){
tree[no]=max(tree[no],val+tree2[no]);
if(l<r){
lazy[no*2+1]=max(lazy[no*2+1],val);
lazy[no*2+2]=max(lazy[no*2+2],val);
}
}
else{
llo mid=(l+r)/2;
update(no*2+1,l,mid,aa,bb,val);
update(no*2+2,mid+1,r,aa,bb,val);
tree[no]=max(tree[no*2+1],tree[no*2+2]);
}
}
llo query(llo no,llo l,llo r,llo aa,llo bb){
push(no,l,r);
if(r<aa or l>bb){
return 0;
}
if(aa<=l and r<=bb){
return tree[no];
}
else{
llo mid=(l+r)/2;
return max(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(llo i=0;i<n;i++){
cin>>it[i];
}
vector<pair<llo,llo>> ss;
for(llo i=0;i<n;i++){
while(ss.size()){
if(ss.back().a<it[i]){
ss.pop_back();
}
else{
break;
}
}
if(ss.size()){
llo ind=i-ss.back().b+i;
if(ind<n){
tt[ss.back().b].pb({i,-1});
//ans=max(ans,it[i]+ss.back().a+aa[ind]);
}
}
ss.pb({it[i],i});
}
ss.clear();
for(llo i=n-1;i>=0;i--){
while(ss.size()){
if(ss.back().a<it[i]){
ss.pop_back();
}
else{
break;
}
}
if(ss.size()){
llo ind=ss.back().b-i+ss.back().b;
if(ind<n){
tt[i].pb({ss.back().b,-1});
//ans=max(ans,it[i]+ss.back().a+aa[ind]);
}
}
ss.pb({it[i],i});
}
llo q;
cin>>q;
for(llo i=0;i<q;i++){
llo cc,dd;
cin>>cc>>dd;
cc--;
dd--;
tt[cc].pb({dd,i});
}
build(0,0,n-1);
for(llo i=n-1;i>=0;i--){
for(auto j:tt[i]){
//cout<<i<<":"<<j.a<<":"<<j.b<<endl;
if(j.b==-1){
llo ind=j.a+j.a-i;
//cout<<ind<<":"<<i<<","<<j.a<<":"<<it[j.a]+it[i]<<endl;
update(0,0,n-1,ind,n-1,it[j.a]+it[i]);
}
else{
ans[j.b]=query(0,0,n-1,i,j.a);
//cout<<j.b<<endl;
}
}
}
for(llo i=0;i<q;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12160 KB |
Output is correct |
2 |
Correct |
8 ms |
12160 KB |
Output is correct |
3 |
Correct |
7 ms |
12160 KB |
Output is correct |
4 |
Correct |
7 ms |
12160 KB |
Output is correct |
5 |
Correct |
8 ms |
12160 KB |
Output is correct |
6 |
Correct |
8 ms |
12160 KB |
Output is correct |
7 |
Correct |
8 ms |
12160 KB |
Output is correct |
8 |
Correct |
7 ms |
12160 KB |
Output is correct |
9 |
Correct |
8 ms |
12160 KB |
Output is correct |
10 |
Correct |
9 ms |
12160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12160 KB |
Output is correct |
2 |
Correct |
8 ms |
12160 KB |
Output is correct |
3 |
Correct |
7 ms |
12160 KB |
Output is correct |
4 |
Correct |
7 ms |
12160 KB |
Output is correct |
5 |
Correct |
8 ms |
12160 KB |
Output is correct |
6 |
Correct |
8 ms |
12160 KB |
Output is correct |
7 |
Correct |
8 ms |
12160 KB |
Output is correct |
8 |
Correct |
7 ms |
12160 KB |
Output is correct |
9 |
Correct |
8 ms |
12160 KB |
Output is correct |
10 |
Correct |
9 ms |
12160 KB |
Output is correct |
11 |
Correct |
416 ms |
39036 KB |
Output is correct |
12 |
Correct |
406 ms |
39036 KB |
Output is correct |
13 |
Correct |
421 ms |
38924 KB |
Output is correct |
14 |
Correct |
457 ms |
39032 KB |
Output is correct |
15 |
Correct |
442 ms |
39032 KB |
Output is correct |
16 |
Correct |
416 ms |
38648 KB |
Output is correct |
17 |
Correct |
412 ms |
38520 KB |
Output is correct |
18 |
Correct |
422 ms |
38392 KB |
Output is correct |
19 |
Correct |
415 ms |
39032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
240 ms |
38008 KB |
Output is correct |
2 |
Correct |
141 ms |
37084 KB |
Output is correct |
3 |
Correct |
132 ms |
37084 KB |
Output is correct |
4 |
Correct |
237 ms |
38008 KB |
Output is correct |
5 |
Correct |
232 ms |
38136 KB |
Output is correct |
6 |
Correct |
259 ms |
37368 KB |
Output is correct |
7 |
Correct |
236 ms |
37240 KB |
Output is correct |
8 |
Correct |
225 ms |
37368 KB |
Output is correct |
9 |
Correct |
231 ms |
37624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12160 KB |
Output is correct |
2 |
Correct |
8 ms |
12160 KB |
Output is correct |
3 |
Correct |
7 ms |
12160 KB |
Output is correct |
4 |
Correct |
7 ms |
12160 KB |
Output is correct |
5 |
Correct |
8 ms |
12160 KB |
Output is correct |
6 |
Correct |
8 ms |
12160 KB |
Output is correct |
7 |
Correct |
8 ms |
12160 KB |
Output is correct |
8 |
Correct |
7 ms |
12160 KB |
Output is correct |
9 |
Correct |
8 ms |
12160 KB |
Output is correct |
10 |
Correct |
9 ms |
12160 KB |
Output is correct |
11 |
Correct |
416 ms |
39036 KB |
Output is correct |
12 |
Correct |
406 ms |
39036 KB |
Output is correct |
13 |
Correct |
421 ms |
38924 KB |
Output is correct |
14 |
Correct |
457 ms |
39032 KB |
Output is correct |
15 |
Correct |
442 ms |
39032 KB |
Output is correct |
16 |
Correct |
416 ms |
38648 KB |
Output is correct |
17 |
Correct |
412 ms |
38520 KB |
Output is correct |
18 |
Correct |
422 ms |
38392 KB |
Output is correct |
19 |
Correct |
415 ms |
39032 KB |
Output is correct |
20 |
Correct |
240 ms |
38008 KB |
Output is correct |
21 |
Correct |
141 ms |
37084 KB |
Output is correct |
22 |
Correct |
132 ms |
37084 KB |
Output is correct |
23 |
Correct |
237 ms |
38008 KB |
Output is correct |
24 |
Correct |
232 ms |
38136 KB |
Output is correct |
25 |
Correct |
259 ms |
37368 KB |
Output is correct |
26 |
Correct |
236 ms |
37240 KB |
Output is correct |
27 |
Correct |
225 ms |
37368 KB |
Output is correct |
28 |
Correct |
231 ms |
37624 KB |
Output is correct |
29 |
Correct |
1644 ms |
100572 KB |
Output is correct |
30 |
Correct |
1390 ms |
97872 KB |
Output is correct |
31 |
Correct |
1340 ms |
97908 KB |
Output is correct |
32 |
Correct |
1624 ms |
100856 KB |
Output is correct |
33 |
Correct |
1608 ms |
100856 KB |
Output is correct |
34 |
Correct |
1754 ms |
98424 KB |
Output is correct |
35 |
Correct |
1648 ms |
98296 KB |
Output is correct |
36 |
Correct |
1621 ms |
97960 KB |
Output is correct |
37 |
Correct |
1653 ms |
99704 KB |
Output is correct |
38 |
Correct |
1104 ms |
99036 KB |
Output is correct |
39 |
Correct |
1118 ms |
98748 KB |
Output is correct |
40 |
Correct |
1080 ms |
95736 KB |
Output is correct |
41 |
Correct |
1069 ms |
94968 KB |
Output is correct |
42 |
Correct |
1090 ms |
95096 KB |
Output is correct |
43 |
Correct |
1116 ms |
96632 KB |
Output is correct |
44 |
Correct |
1215 ms |
99160 KB |
Output is correct |
45 |
Correct |
1215 ms |
99160 KB |
Output is correct |
46 |
Correct |
1195 ms |
95992 KB |
Output is correct |
47 |
Correct |
1229 ms |
95608 KB |
Output is correct |
48 |
Correct |
1234 ms |
95608 KB |
Output is correct |
49 |
Correct |
1182 ms |
97528 KB |
Output is correct |
50 |
Correct |
1284 ms |
99960 KB |
Output is correct |
51 |
Correct |
1379 ms |
99960 KB |
Output is correct |
52 |
Correct |
1409 ms |
97400 KB |
Output is correct |
53 |
Correct |
1313 ms |
97144 KB |
Output is correct |
54 |
Correct |
1307 ms |
97144 KB |
Output is correct |
55 |
Correct |
1327 ms |
98808 KB |
Output is correct |