#include <bits/stdc++.h>
using namespace std;
#define int long long
long long arr[500005];
struct node{
int s,e,m;
long long val,con,suf;
node *l, *r;
node(int S, int E){
s=S; e=E; m=(s+e)/2;
val=con=0;
suf=arr[s];
if(s!=e){
l=new node(S,m);
r=new node(m+1,E);
suf=max(l->suf,r->suf);
}
}
void update(int S, long long V){
if(s==e){
con=max(con,V);
val=con+suf;
return;
}
if(S<=m) l->update(S,V);
else r->update(S,V);
con=max(l->con,r->con);
val=max({l->val,r->val,l->con+r->suf});
}
pair<long long,pair<long long,long long> > query(int S, int E){
if(S<=s&&e<=E) return {val,{con,suf}};
if(E<=m) return l->query(S,E);
else if(S>m) return r->query(S,E);
else{
pair<long long,pair<long long,long long> > a=l->query(S,m),b=r->query(m+1,E),ret;
ret.first=max({a.first,b.first,a.second.first+b.second.second});
ret.second.first=max(a.second.first,b.second.first);
ret.second.second=max(a.second.second,b.second.second);
return ret;
}
}
} *root;
int32_t main(){
ios::sync_with_stdio(0);cin.tie(0);
int n;
cin >> n;
for(int i=0; i<n; i++) cin >> arr[i];
root=new node(0,n-1);
int q;
cin >> q;
vector<pair<long long,int> > mono;
vector<pair<pair<int,int>,long long> > yay;
for(int i=0; i<n; i++){
while(!mono.empty()&&mono.back().first<=arr[i]){
int a=mono.back().second;
if(i*2-a<n) yay.push_back({{a,i*2-a},arr[a]+arr[i]});
mono.pop_back();
}
if(!mono.empty()){
int a=mono.back().second;
if(i*2-a<n) yay.push_back({{a,i*2-a},arr[a]+arr[i]});
}
mono.push_back({arr[i],i});
}
sort(yay.begin(),yay.end());
pair<pair<int,int>,int> qu[q];
for(int i=0; i<q; i++){
cin >> qu[i].first.first >> qu[i].first.second;
qu[i].first.first--; qu[i].first.second--;
qu[i].second=i;
}
sort(qu,qu+q,greater<pair<pair<int,int>,int> >());
long long ans[q];
for(int i=0; i<q; i++){
while(!yay.empty()&&yay.back().first.first>=qu[i].first.first){
root->update(yay.back().first.second,yay.back().second);
yay.pop_back();
}
ans[qu[i].second]=root->query(0,qu[i].first.second).first;
}
for(int i=0; i<q; i++) cout << ans[i] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
112 ms |
48372 KB |
Output is correct |
2 |
Correct |
70 ms |
43204 KB |
Output is correct |
3 |
Correct |
71 ms |
44640 KB |
Output is correct |
4 |
Correct |
110 ms |
48572 KB |
Output is correct |
5 |
Correct |
108 ms |
49600 KB |
Output is correct |
6 |
Correct |
104 ms |
47548 KB |
Output is correct |
7 |
Correct |
107 ms |
47984 KB |
Output is correct |
8 |
Correct |
108 ms |
47564 KB |
Output is correct |
9 |
Correct |
108 ms |
47900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |