//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
const int maxn = 5e5+10;
int n;
int a[maxn];
deque <int> q;
vector <int> good[maxn];
pii tree[maxn*4];
int add[maxn*4];
vector <pair<pii,int> > que;
int ans[maxn];
void init(int c,int cl,int cr) {
if (cl==cr) tree[c] = {a[cl],a[cl]},add[c] = 0;
else {
int mid=cl+cr>>1;
init(c<<1,cl,mid);
init(c<<1|1,mid+1,cr);
int tmp = max(tree[c<<1].fi,tree[c<<1|1].fi);
tree[c] = {tmp,tmp};
}
}
void push_down(int c) {
tree[c<<1].fi = max(tree[c<<1].fi,tree[c<<1].se+add[c]);
add[c<<1] = max(add[c<<1],add[c]);
tree[c<<1|1].fi = max(tree[c<<1|1].fi,tree[c<<1|1].se+add[c]);
add[c<<1|1] = max(add[c<<1|1],add[c]);
add[c] = 0;
}
void update(int c,int cl,int cr,int l,int r,int val) {
if (l<=cl and cr<=r) {
tree[c].fi = max(tree[c].fi,tree[c].se+val);
add[c] = max(add[c],val);
return;
}
int mid=cl+cr>>1;
if (add[c]!=0) push_down(c);
if (l<=mid) update(c<<1,cl,mid,l,r,val);
if (r>mid) update(c<<1|1,mid+1,cr,l,r,val);
tree[c].fi = max(tree[c<<1].fi,tree[c<<1|1].fi);
return;
}
int query(int c,int cl,int cr,int l,int r) {
if (l<=cl and cr<=r) return tree[c].fi;
int mid=cl+cr>>1;
if (add[c]!=0) push_down(c);
int ret = 0;
if (l<=mid) ret = query(c<<1,cl,mid,l,r);
if (r>mid) ret = max(ret,query(c<<1|1,mid+1,cr,l,r));
return ret;
}
int main() {
// freopen("input.txt","r",stdin);
std::ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
rep(i,1,n+1) cin>>a[i];
for (int i=n;i>0;i--) {
while (!q.empty() and a[q.back()]<=a[i]) good[i].pb(q.back()),q.pop_back();
if (!q.empty()) good[i].pb(q.back());
q.push_back(i);
while (SZ(q)>2) q.pop_front();
}
// rep(i,1,n+1) for (auto it:good[i]) cout<<i<<" "<<it<<endl;
init(1,1,n);
int _;cin>>_;
rep(i,0,_) {
int l,r;
cin>>l>>r;
que.pb({{l,r},i});
}
sort(ALL(que));reverse(ALL(que));
int l=n;
rep(i,0,_) {
while (l>=que[i].fi.fi) {
for (auto r:good[l]) if (r+r-l<=n) update(1,1,n,r+r-l,n,a[l]+a[r]);
l--;
}
ans[que[i].se] = query(1,1,n,que[i].fi.fi,que[i].fi.se);
}
rep(i,0,_) cout<<ans[i]<<"\n";
return 0;
}
Compilation message
jumps.cpp: In function 'void init(int, int, int)':
jumps.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid=cl+cr>>1;
| ~~^~~
jumps.cpp: In function 'void update(int, int, int, int, int, int)':
jumps.cpp:61:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid=cl+cr>>1;
| ~~^~~
jumps.cpp: In function 'int query(int, int, int, int, int)':
jumps.cpp:71:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int mid=cl+cr>>1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
12052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
12052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
27016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11988 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
12052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
