#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<long double, ll> pp;
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353, maxn = 5e5 + 5, lg = 19, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
ll a[maxn];
int n, q;
void slv1_2(){
vector<vector<ll>> mx(n, vector<ll>(n, -inf));
rep(i,0,n){
mx[i][i] = a[i];
rep(j,i+1,n) mx[i][j] = max(mx[i][j-1], a[j]);
}
vector<vector<ll>> ans(n, vector<ll>(n, -inf));
rep(l,3,n+1){
rep(i,0,n-l+1){
int j = i + l - 1;
ans[i][j] = max({ans[i+1][j], ans[i][j-1], a[i] + a[j] + mx[i+1][(i+j)>>1]});
}
}
while(q--){
int l, r; cin >> l >> r;
cout << ans[--l][--r] << '\n';
}
}
template<class T> struct Rmq{
vector<vector<T>> rmq;
vector<int> lgg;
T comb(T a, T b){
return max(a, b);
}
Rmq(vector<T> a){
int n = sz(a);
lgg.resize(n + 1);
rep(i,2,n + 1) lgg[i] = lgg[i>>1] + 1;
rmq.assign(lgg[n] + 1, vector<T>(n));
rmq[0] = a;
rep(i,1,lgg[n] + 1){
rep(j,0,n-(1<<i)+1){
rmq[i][j] = comb(rmq[i-1][j], rmq[i-1][j + (1 << (i-1))]);
}
}
}
T get(int l, int r){ // 0-base [l, r]
int g = lgg[r - l + 1];
return comb(rmq[g][l], rmq[g][r - (1<<g) + 1]);
}
};
void slv3(){
int l, r; cin >> l >> r; l--, r--, n = r - l + 1;
vector<int> b(a + l, a + r + 1);
Rmq<int> rmq(b);
auto get_max = [&](int l, int r){
if(l > r || r < 0) return -1;
l = max(0, l), r = min(r, n-1);
return rmq.get(l, r);
};
auto clc = [&](int i){
ll res = -inf;
// right
rep(j,0,i) res = max(res, 1ll*b[i] + b[j] + get_max(j-(i-j),j-1));
// center
rep(j,0,i) res = max(res, 1ll*b[i] + b[j] + get_max(i+(i-j),n-1));
// left
rep(j,i+1,n) res = max(res, 1ll*b[i] + b[j] + get_max(j+(j-i),n-1));
return res;
};
vector<int> c(n); iota(all(c), 0), sort(all(c), [&](int i, int j){ return b[i] > b[j]; });
ll ans = 0; int g = min(int(log2(n))+3, n);
rep(i,0,g){
ans = max(ans, clc(c[i]));
}
cout << ans << '\n';
}
struct LazySegment{
vector<ll> seg, vl, laz;
int n;
void init(int _n, vector<ll> a = {}){
n = _n;
seg.assign(n<<2, 0), laz.assign(n<<2, 0), vl.assign(n<<2, 0); // init
if(sz(a)) build(a, 1, 0, n);
}
void updNode(int x, ll k){
seg[x] = max(vl[x] + k, seg[x]), laz[x] = max(laz[x], k);
}
void build(const vector<ll>& a, int x, int lx, int rx){
if(lx + 1 == rx){
seg[x] = vl[x] = a[lx];
return;
}
int mid = (lx + rx)>>1;
build(a, x<<1, lx, mid), build(a, x<<1|1, mid, rx);
seg[x] = vl[x] = max(seg[x<<1], seg[x<<1|1]);
}
void shift(int x){
if(laz[x]){
updNode(x<<1, laz[x]);
updNode(x<<1|1, laz[x]);
laz[x] = 0;
}
}
void upd(int l, int r, ll a, int x, int lx, int rx){
if(l <= lx && r >= rx){
updNode(x, a);
return;
} if(l >= rx || r <= lx) return;
shift(x); int mid = (lx + rx)>>1;
upd(l, r, a, x<<1, lx, mid), upd(l, r, a, x<<1|1, mid, rx);
seg[x] = max(seg[x<<1], seg[x<<1|1]);
}
void upd(int l, int r, ll a){ upd(l, r, a, 1, 0, n); }
ll get(int l, int r, int x, int lx, int rx){
if(l <= lx && r >= rx) return seg[x];
if(l >= rx || r <= lx) return -1; // init
shift(x); int mid = (lx + rx)>>1;
return max(get(l, r, x<<1, lx, mid), get(l, r, x<<1|1, mid, rx));
}
ll get(int l, int r){ return get(l, r, 1, 0, n); }
};
void slv4(){
vector<vector<pp>> st(n);
vector<ll> ans(q);
rep(i,0,q){
int l, r; cin >> l >> r; l--, r--;
st[l].pb({r, i});
}
vector<int> stk;
LazySegment seg;
seg.init(n, vector<ll>(a, a + n));
per(i,n-1,0){
vector<int> candj;
while(sz(stk) && a[stk.back()] < a[i]) candj.pb(stk.back()), stk.pop_back();
if(sz(stk)) candj.pb(stk.back());
stk.pb(i);
for(int j: candj){
int k = j+j-i;
if(k > n) continue;
seg.upd(k, n, a[i] + a[j]);
}
for(auto[r,id]: st[i]) ans[id] = seg.get(i, r+1);
}
for(ll c: ans) cout << c << '\n';
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cin >> n;
rep(i,0,n) cin >> a[i];
cin >> q;
slv4();
return 0;
}
Compilation message
jumps.cpp: In function 'void slv4()':
jumps.cpp:163:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
163 | for(auto[r,id]: st[i]) ans[id] = seg.get(i, r+1);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
317 ms |
35948 KB |
Output is correct |
12 |
Correct |
276 ms |
35904 KB |
Output is correct |
13 |
Correct |
268 ms |
36000 KB |
Output is correct |
14 |
Correct |
313 ms |
36088 KB |
Output is correct |
15 |
Correct |
269 ms |
35984 KB |
Output is correct |
16 |
Correct |
297 ms |
35356 KB |
Output is correct |
17 |
Correct |
313 ms |
35388 KB |
Output is correct |
18 |
Correct |
277 ms |
35260 KB |
Output is correct |
19 |
Correct |
278 ms |
35808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
158 ms |
26964 KB |
Output is correct |
2 |
Correct |
93 ms |
27140 KB |
Output is correct |
3 |
Correct |
88 ms |
26876 KB |
Output is correct |
4 |
Correct |
152 ms |
26860 KB |
Output is correct |
5 |
Correct |
177 ms |
26844 KB |
Output is correct |
6 |
Correct |
146 ms |
26856 KB |
Output is correct |
7 |
Correct |
155 ms |
26868 KB |
Output is correct |
8 |
Correct |
163 ms |
26964 KB |
Output is correct |
9 |
Correct |
162 ms |
26964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
317 ms |
35948 KB |
Output is correct |
12 |
Correct |
276 ms |
35904 KB |
Output is correct |
13 |
Correct |
268 ms |
36000 KB |
Output is correct |
14 |
Correct |
313 ms |
36088 KB |
Output is correct |
15 |
Correct |
269 ms |
35984 KB |
Output is correct |
16 |
Correct |
297 ms |
35356 KB |
Output is correct |
17 |
Correct |
313 ms |
35388 KB |
Output is correct |
18 |
Correct |
277 ms |
35260 KB |
Output is correct |
19 |
Correct |
278 ms |
35808 KB |
Output is correct |
20 |
Correct |
158 ms |
26964 KB |
Output is correct |
21 |
Correct |
93 ms |
27140 KB |
Output is correct |
22 |
Correct |
88 ms |
26876 KB |
Output is correct |
23 |
Correct |
152 ms |
26860 KB |
Output is correct |
24 |
Correct |
177 ms |
26844 KB |
Output is correct |
25 |
Correct |
146 ms |
26856 KB |
Output is correct |
26 |
Correct |
155 ms |
26868 KB |
Output is correct |
27 |
Correct |
163 ms |
26964 KB |
Output is correct |
28 |
Correct |
162 ms |
26964 KB |
Output is correct |
29 |
Correct |
1091 ms |
93588 KB |
Output is correct |
30 |
Correct |
918 ms |
97644 KB |
Output is correct |
31 |
Correct |
852 ms |
93516 KB |
Output is correct |
32 |
Correct |
1025 ms |
93688 KB |
Output is correct |
33 |
Correct |
1048 ms |
93644 KB |
Output is correct |
34 |
Correct |
1025 ms |
92884 KB |
Output is correct |
35 |
Correct |
1022 ms |
92852 KB |
Output is correct |
36 |
Correct |
1022 ms |
92952 KB |
Output is correct |
37 |
Correct |
1028 ms |
93508 KB |
Output is correct |
38 |
Correct |
707 ms |
95436 KB |
Output is correct |
39 |
Correct |
714 ms |
95464 KB |
Output is correct |
40 |
Correct |
689 ms |
94400 KB |
Output is correct |
41 |
Correct |
692 ms |
94308 KB |
Output is correct |
42 |
Correct |
694 ms |
94416 KB |
Output is correct |
43 |
Correct |
677 ms |
94472 KB |
Output is correct |
44 |
Correct |
743 ms |
95916 KB |
Output is correct |
45 |
Correct |
746 ms |
95948 KB |
Output is correct |
46 |
Correct |
737 ms |
94796 KB |
Output is correct |
47 |
Correct |
751 ms |
94816 KB |
Output is correct |
48 |
Correct |
706 ms |
94796 KB |
Output is correct |
49 |
Correct |
724 ms |
95488 KB |
Output is correct |
50 |
Correct |
810 ms |
96844 KB |
Output is correct |
51 |
Correct |
814 ms |
96784 KB |
Output is correct |
52 |
Correct |
800 ms |
96112 KB |
Output is correct |
53 |
Correct |
800 ms |
96000 KB |
Output is correct |
54 |
Correct |
804 ms |
95924 KB |
Output is correct |
55 |
Correct |
799 ms |
96656 KB |
Output is correct |