#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 5e5 + 23;
const ll inf = 1e18;
#define F first
#define S second
#define pb push_back
#define sz(x) ((int)x.size())
#define kill(x) cout<<x , exit(0);
#define all(x) x.begin(),x.end()
#define lc (v<<1)
#define rc ((v<<1)|1)
#define debug(x) cerr<< #x << " : " << x << '\n';
#define int ll
struct Seg {
int t[N<<2];
int mx[N<<2];
int lz[N<<2];
Seg() {
for(int i = 0 ; i<(N<<2); i ++) t[i] = mx[i] = lz[i] = 0;
}
void shift(int v) {
if(lz[v] == 0) return;
lz[lc] = max(lz[lc],lz[v]);
lz[rc] = max(lz[rc],lz[v]);
t[lc] = max(t[lc],mx[lc] + lz[lc]);
t[rc] = max(t[rc],mx[rc] + lz[rc]);
lz[v] = 0;
}
// khode a[i] ha
void set(int pos,int x,int v=1,int tl= 1,int tr= N) {
if(tr-tl == 1) {
mx[v] = x;
return;
}
int mid=(tl+tr)/2;
if(pos < mid)
set(pos,x,lc,tl,mid);
else
set(pos,x,rc,mid,tr);
mx[v] = max(mx[lc],mx[rc]);
}
void add(int l,int r,int x,int v=1,int tl = 1,int tr= N) {
if(l > r) return;
if(l == tl && r ==tr-1) {
lz[v] = max(lz[v],x);
t[v] = max(t[v],mx[v] + lz[v]);
return;
}
shift(v);
int mid=(tl+tr)/2;
add(l,min(mid-1,r),x,lc,tl,mid);
add(max(l,mid),r,x,rc,mid,tr);
t[v] = max(t[lc],t[rc]);
}
int get(int l,int r,int v=1,int tl=1,int tr = N) {
if(l >r) return 0;
if(l == tl && r == tr-1) return t[v];
shift(v);
int mid=(tl+tr)/2;
return max(get(l,min(mid-1,r),lc,tl,mid), get(max(l,mid),r,rc,mid,tr));
}
}seg;
int n,q;
int a[N];
vector<pair<int,int>> Q[N];
vector<pair<int,int>> here[N];
int ans[N];
vector<int> st;
int L[N],R[N];
vector<pair<int,int> > edges;
int Mx[N];
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n;
for(int i = 1; i<= n ; i ++) {
cin>>a[i];
seg.set(i,a[i]);
}
cin>>q;
for(int i = 0 ; i< q; i ++) {
int l,r; cin>>l>>r;
Q[l].pb({r,i});
}
st.pb(0);
for(int i = 1; i<= n ; i++) {
while(st.back() && a[st.back()] < a[i]) st.pop_back();
if(sz(st) > 1) {
L[i] = st.back();
}
st.pb(i);
} st.clear();
st.pb(0);
for(int i = n ; i >= 1;i --) {
while(st.back() && a[st.back()] < a[i]) st.pop_back();
if(sz(st) > 1) {
R[i]= st.back();
}
st.pb(i);
}
for(int i= 1; i <= n ; i ++) {
if(R[i] != 0 && R[i] - i + R[i] <= n) {
//Mx[R[i]-i+R[i]] = max(Mx[R[i]-i +R[i]], a[i] + a[R[i]]);
here[i].pb({R[i]-i+R[i],a[i] + a[R[i]]});
}
if(L[i] != 0 && i-L[i] + i <= n) {
//Mx[i-L[i]+i] = max(Mx[i-L[i]+i],a[i] + a[L[i]]);
here[L[i]].pb({i-L[i]+i,a[i] + a[L[i]]});
}
}
for(int i = n; i >= 1; i --) {
for(auto [l,val] : here[i]) seg.add(l,n,val);
for(auto [r,id] : Q[i]) ans[id] = seg.get(i,r);
}
for(int i = 0 ; i< q;i ++) {
cout<<ans[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
77916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
77916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
77916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
