#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const int N=5*1e5+50,inf=1e9;
int a[N];
int root,nc,lc[2*N],rc[2*N],maks[2*N],maks1[2*N],maksu[2*N],lazy[2*N];
void Build(int &c,int ss,int se){
c=++nc;
maks[c]=lazy[c]=-inf;
if(ss==se){
maks1[c]=a[ss];
maksu[c]=maks1[c];
return;
}
int mid=(ss+se)/2;
Build(lc[c],ss,mid);
Build(rc[c],mid+1,se);
maks1[c]=max(maks1[lc[c]],maks1[rc[c]]);
maksu[c]=maks1[c];
}
void update(int c,int qval){
lazy[c]=max(lazy[c],qval);
maks[c]=max(maks[c],qval);
maksu[c]=max(maksu[c],maks1[c]+qval);
}
void push(int c){
update(lc[c],lazy[c]);
update(rc[c],lazy[c]);
lazy[c]=-inf;
}
void Update(int c,int ss,int se,int qs,int qe,int qval){
//if(!c) c=++nc;
if(qs>qe) return;
if(qs<=ss && se<=qe){
update(c,qval);
//printf("%i %i %i: %i %i %i\n",c,ss,se,maks[c],maks1[c],maksu[c]);
return;
}
if(qe<ss || se<qs) return;
int mid=(ss+se)/2;
push(c);
Update(lc[c],ss,mid,qs,qe,qval);
Update(rc[c],mid+1,se,qs,qe,qval);
maks[c]=max(maks[lc[c]],maks[rc[c]]);
maksu[c]=max(maksu[lc[c]],maksu[rc[c]]);
//printf("%i %i %i: %i %i %i\n",c,ss,se,maks[c],maks1[c],maksu[c]);
}
int Get(int c,int ss,int se,int qs,int qe){
//printf("%i %i: %i %i %i %i\n",ss,se,maks[c],maks1[c],maksu[c],lazy[c]);
if(qs<=ss && se<=qe) {
return maksu[c];
}
if(qe<ss || se<qs) return -inf;
int mid=(ss+se)/2;
push(c);
return max(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
int main()
{
int n;scanf("%i",&n);
for(int i=1;i<=n;i++)scanf("%i",&a[i]);
int Q;scanf("%i",&Q);pair<pair<int,int>,int>Qs[Q+10];
for(int i=1;i<=Q;i++) {scanf("%i%i",&Qs[i].fi.fi,&Qs[i].fi.se);Qs[i].se=i;}
vector<int>mono;
vector<int>R[n+10];
for(int i=1;i<=n;i++){
while(mono.size() && a[mono.back()]<a[i]){
R[mono.back()].pb(i);
mono.pop_back();
}
if(mono.size() && a[mono.back()]==a[i]){R[mono.back()].pb(i);mono.pop_back();}
mono.pb(i);
}
mono.clear();
for(int i=1;i<=n;i++){
while(mono.size() && a[mono.back()]>a[i]){
R[mono.back()].pb(i);
int temp=mono.back();
mono.pop_back();
while(mono.size() && a[mono.back()]==a[temp]) mono.pop_back();
}
mono.pb(i);
}
//printf("*\n");
//for(int i=1;i<=n;i++) for(auto j:R[i]) printf("%i %i\n",i,j);
/*vector<int>R[n+10];
for(int i=1;i<=n;i++){
//printf("%i: ",i);
//int mx=a[i];
for(int j=i+1;j<=n;j++){
//mx=max(mx,a[j]);
int mx=0;
for(int k=i+1;k<j;k++){
mx=max(mx,a[k]);
}
if(mx<a[i] && mx<a[j]) R[i].pb(j);//printf("%i ",R[i].back());}
}
//printf("\n");
}*/
Build(root,1,n);
int res[Q+10]={0};
sort(Qs+1,Qs+Q+1);
for(int i=n,j=Q;i>=1;i--){
for(auto j:R[i]){//if(R[i]!=0){
//a=i,b=R[i], b-a<=c-b, 2b-a=2R[i]-i<=c
if(2*j-i<=n) Update(root,1,n,2*j-i,n,a[i]+a[j]);//printf("%i %i %i %i: %i\n",i,j,2*j-i,n,a[i]+a[j]);}
}
while(j>=1 && Qs[j].fi.fi==i){
res[Qs[j].se]=Get(root,1,n,Qs[j].fi.fi,Qs[j].fi.se);
//printf("%i %i %i %i\n",res[Qs[j].se],Qs[j].fi.fi,Qs[j].fi.se,Qs[j].se);
j--;
}
//if(i==3) printf("- %i -\n",Get(root,1,n,3,5));
}
for(int i=1;i<=Q;i++) printf("%i ",res[i]);
return 0;
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:63:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | int n;scanf("%i",&n);
| ~~~~~^~~~~~~~~
jumps.cpp:64:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | for(int i=1;i<=n;i++)scanf("%i",&a[i]);
| ~~~~~^~~~~~~~~~~~
jumps.cpp:65:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | int Q;scanf("%i",&Q);pair<pair<int,int>,int>Qs[Q+10];
| ~~~~~^~~~~~~~~
jumps.cpp:66:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | for(int i=1;i<=Q;i++) {scanf("%i%i",&Qs[i].fi.fi,&Qs[i].fi.se);Qs[i].se=i;}
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
159 ms |
36176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
