#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("VNOICUP.INP");
ofstream fout("VNOICUP.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
//const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 5e5 + 5, mxm = 1e5, sq = 400, mxv = 1e6 + 5;
const int base = (1 << 18);
const ll inf = 4e9, neg = -69420, test = 1e5;
//const int p[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};bool ck[mxn + 1];
struct Node{
ll ab = -inf, abc = -inf, lz = -inf;
};
ll a[mxn + 5], ans[mxn + 5];
vt<pii>special[mxn + 1], queries[mxn + 1];
Node st[4 * mxn + 1];
void change(int nd, ll c){
st[nd].lz = max(st[nd].lz, c);
st[nd].abc = max(st[nd].abc, st[nd].ab + c);
}
void push(int nd){
change(nd << 1, st[nd].lz); change(nd << 1 | 1, st[nd].lz);
st[nd].lz = -inf;
}
void upd(int nd, int l, int r, int id, ll v){
if(id < l || id > r)return;
if(l == r){
st[nd].ab = max(st[nd].ab, v);
return;
}
int mid = (l + r) >> 1;
push(nd);
upd(nd << 1, l, mid, id, v); upd(nd << 1 | 1, mid + 1, r, id, v);
st[nd].ab = max(st[nd << 1].ab, st[nd << 1 | 1].ab);
}
void updc(int nd, int l, int r, int ql, int qr, ll v){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
change(nd, v);
return;
}
int mid = (l + r) >> 1;
push(nd);
updc(nd << 1, l, mid, ql, qr, v); updc(nd << 1 | 1, mid + 1, r, ql, qr, v);
st[nd].abc = max(st[nd << 1].abc, st[nd << 1 | 1].abc);
}
ll get(int nd, int l, int r, int ql, int qr){
if(ql > r || qr < l)return(-inf);
if(ql <= l && qr >= r){
return(st[nd].abc);
}
int mid = (l + r) >> 1;
push(nd);
return(max(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
int n;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)cin >> a[i];
deque<int>dq;
dq.pb(n);
for(int i = n - 1; i >= 1; i--){
for(int j = 0; j < sz(dq); j++){
special[2 * dq[j] - i].pb(make_pair(i, a[i] + a[dq[j]]));
}
while(sz(dq) && a[dq.back()] <= a[i])dq.pop_back();
if(i && a[i - 1] <= a[i]){
while(sz(dq))dq.pop_back();
}
dq.pb(i);
}
int q; cin >> q;
for(int i = 0; i < q; i++){
int l, r; cin >> l >> r;
queries[r].pb({l, i});
}
for(int i = 1; i <= n; i++){
for(auto j: special[i]){
//cout << i << " " << j.first << ' ' << j.second << "\n";
upd(1, 1, n, j.first, j.second);
}
updc(1, 1, n, 1, i, a[i]);
for(auto [l, id]: queries[i]){
ans[id] = get(1, 1, n, l, i);
}
}
for(int i = 0; i < q; i++){
cout << ans[i] << "\n";
}
return(0);
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:101:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
101 | for(auto [l, id]: queries[i]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
45636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
23764 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
