#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
const int N = 5e5+5, inf = 1e16, mod = 1e9+7;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
struct node{
int ans, ab, c;
node operator +(node nw){
chmax(ans, nw.ans);
chmax(ab, nw.ab);
chmax(c, nw.c);
return *this;
}
};
struct segtree{
vector<node> t;
vector<int> b;
segtree(){
t.resize(N*4);
b.resize(N*4, 0);
};
void build(int i, int l, int r, vector<int> &a){
if(l == r){
t[i] = {a[l], 0ll, a[l]};
return;
}
int m = (l+r)>>1;
build(i*2, l, m, a);
build(i*2+1, m+1, r, a);
t[i] = t[i*2] + t[i*2+1];
};
void push(int i, int l, int r){
if(l!=r){
chmax(b[i*2],b[i]);
chmax(b[i*2+1],b[i]);
}
chmax(t[i].ab, b[i]);
chmax(t[i].ans, b[i] + t[i].c);
b[i] = 0;
return;
};
void upd(int i, int tl, int tr, int l, int r, int val){
push(i, l, r);
if(l > tr || r < tl)return;
if(tl <= l && r <= tr){
b[i] = val;
push(i,l,r);
return;
}
int m = (l+r)>>1;
upd(i*2, tl, tr, l, m, val);
upd(i*2+1, tl, tr, m+1, r, val);
t[i] = t[i] + t[i*2];
t[i] = t[i] + t[i*2+1];
return;
};
int get(int i, int l, int r, int tl, int tr){
push(i, l, r);
if(l > tr || r < tl)return 0ll;
if(tl <= l && r <= tr)return t[i].ans;
int m = (l+r)>>1;
return max(
get(i*2, l, m, tl, tr),
get(i*2+1, m+1, r, tl, tr)
);
}
};
segtree T;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int> a(n+1);
for(int i = 1; i <= n; i++)cin >> a[i];
T.build(1, 1, n, a);
vector<vector<pair<int,int>>> qq(n+1);
int q;cin >> q;
for(int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
qq[l].pb({r, i});
}
vector<int> ans(q+1);
vector<pair<int,int>> cur;
for(int i = n; i > 0; i--){
while(cur.size() && cur.back().ff < a[i]){
int A = i, B = cur.back().ss;
if(2*B-A <= n)T.upd(1, 2*B-A, n, 1, n, a[A] + a[B]);
cur.pop_back();
}
if(cur.size()){
int A = i, B = cur.back().ss;
if(2*B-A <= n)T.upd(1, 2*B-A, n, 1, n, a[A] + a[B]);
}
cur.pb({a[i], i});
for(auto j:qq[i]){
ans[j.ss] = T.get(1, 1, n, i, j.ff);
}
}
for(int i = 0; i < q; i++)cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
63068 KB |
Output is correct |
| 2 |
Incorrect |
32 ms |
63052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
63068 KB |
Output is correct |
| 2 |
Incorrect |
32 ms |
63052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
198 ms |
70896 KB |
Output is correct |
| 2 |
Correct |
83 ms |
75204 KB |
Output is correct |
| 3 |
Correct |
124 ms |
70900 KB |
Output is correct |
| 4 |
Correct |
135 ms |
71076 KB |
Output is correct |
| 5 |
Correct |
155 ms |
71088 KB |
Output is correct |
| 6 |
Correct |
150 ms |
70172 KB |
Output is correct |
| 7 |
Correct |
137 ms |
70140 KB |
Output is correct |
| 8 |
Correct |
143 ms |
70228 KB |
Output is correct |
| 9 |
Correct |
135 ms |
70420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
63068 KB |
Output is correct |
| 2 |
Incorrect |
32 ms |
63052 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
