#include <bits/stdc++.h>
using namespace std;
const int N = 5e5;
const int inf = 1e9;
int v[N];
struct query{
int l,r,id;
}queries[N];
stack <int> v2,v3;
int l[N],l2[N];
int ans[N];
int n;
struct nod{
int maxx,maxx2,ans;
}seg[4*N];
nod operator+(nod a,nod b){
return {max(a.maxx,b.maxx),max(a.maxx2,b.maxx2),max(max(a.ans,b.ans),a.maxx2 + b.maxx)};
}
void build(int l,int r,int node = 1){
if(l == r){
seg[node] = {v[l],-inf,-inf};
}else{
int mij = (l + r)/2;
build(l,mij,node*2);
build(mij + 1,r,node*2 + 1);
seg[node] = seg[node*2] + seg[node*2 + 1];
}
}
void add(int pos,int val,int l = 0,int r = n - 1,int node = 1){
//if(l == 0 && r == n - 1)cout<<pos<<' '<<val<<'\n';
if(l == r){
seg[node].maxx2 = max(seg[node].maxx2,val);
seg[node].ans = max(seg[node].maxx + seg[node].maxx2,seg[node].ans);
}else{
int mij = (l + r)/2;
if(pos <= mij){
add(pos,val,l,mij,node*2);
}else{
add(pos,val,mij + 1,r,node*2 + 1);
}
seg[node] = seg[node*2] + seg[node*2 + 1];
}
}
nod get(int ql,int qr,int l = 0,int r = n - 1,int node = 1){
//if(l == 0 && r == n - 1)cout<<ql<<' '<<qr<<'\n';
if(ql <= l && r <= qr){
//cout<<node<<' '<<seg[node].maxx<<' '<<seg[node].maxx2<<' '<<seg[node].ans<<'\n';
return seg[node];
}else{
int mij = (l + r)/2;
if(qr <= mij){
return get(ql,qr,l,mij,node*2);
}else if(mij < ql){
return get(ql,qr,mij + 1,r,node*2 + 1);
}else{
return get(ql,mij,l,mij,node*2) + get(mij + 1,qr,mij + 1,r,node*2 + 1);
}
}
}
void display(int l = 0,int r = n - 1,int node = 1){
if(l != r){
int mij = (l + r)/2;
display(l,mij,node*2);
display(mij + 1,r,node*2 + 1);
seg[node] = seg[node*2] + seg[node*2 + 1];
}
cout<<l<<' '<<r<<' '<<seg[node].maxx<<' '<<seg[node].maxx2<<' '<<seg[node].ans<<'\n';
}
int main(){
int i,j,q,p;
cin>>n;p = n - 1;
for(i = 0;i < n;i++)cin>>v[i];
build(0,n - 1);
//display();
for(i = 0;i < n;i++){
///check
while(!v2.empty() && v[v2.top()] <= v[i]){
l[v2.top()] = i;v2.pop();
}
while(!v3.empty() && v[v3.top()] >= v[i]){
l2[v3.top()] = i;v3.pop();
}
///add
v2.push(i);
v3.push(i);
}
while(!v2.empty()){
l[v2.top()] = -1;
v2.pop();
}
while(!v3.empty()){
l2[v3.top()] = -1;
v3.pop();
}
cin>>q;
for(i = 0;i < q;i++){
queries[i].id = i;
cin>>queries[i].l>>queries[i].r;queries[i].l--;queries[i].r--;
}
sort(queries,queries + q,[&](query a,query b){
return a.l > b.l;
});
for(i = 0;i < q;i++){
while(p >= queries[i].l){
if(l2[p] != -1 && l2[p] + l2[p] - p <= n - 1)add(l2[p] + l2[p] - p,v[l2[p]] + v[p]);
if(l[p] != -1 && l[p] + l[p] - p <= n - 1)add(l[p] + l[p] - p,v[l[p]] + v[p]);
p--;
}
//display();
ans[queries[i].id] = get(queries[i].l,queries[i].r).ans;
}
for(i = 0;i < q;i++)cout<<ans[i]<<'\n';
return 0;
}
/**
15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
3
1 15
3 12
11 14
**/
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:70:11: warning: unused variable 'j' [-Wunused-variable]
70 | int i,j,q,p;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
10576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
