#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 5e5 + 9;
const ll Log2 = 20;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
struct Query{
ll R,id;
};
vector<Query> q[N];
vector<ll> cand[N];
ll n,a[N],Q,L,R,lazy[4*N],ans[N];
stack<ll> S;
struct Node{
ll inc,val,ans;
};
Node st[4*N];
Node operator + (Node a,Node b){
Node res;
res.ans = max(a.ans,max(b.ans,a.inc + b.val));
res.inc = max(a.inc,b.inc);
res.val = max(a.val,b.val);
return res;
}
void Pass(ll id){
ll t = lazy[id];
lazy[id*2] = max(lazy[id*2],t); lazy[id*2 + 1] = max(lazy[id*2 + 1],t);
st[id*2].inc = max(st[id*2].inc,t); st[id*2 + 1].inc = max(st[id*2 + 1].inc,t);
st[id*2].ans = max(st[id*2].ans,t + st[id*2].val);
st[id*2 + 1].ans = max(st[id*2 + 1].ans,t + st[id*2 + 1].val);
}
void upd_inc(ll id,ll l,ll r,ll u,ll v,ll gt){
if (v < l||r < u) return;
//if (u == 4&&v == 6&> == 22) cout<<lazy[id]<<"x\n";
if (u <= l&&r <= v){
st[id].inc = max(st[id].inc,gt); lazy[id] = max(lazy[id],gt);
st[id].ans = max(st[id].ans,gt + st[id].val);
return;
}
ll mid = (l + r)/2; Pass(id);
upd_inc(id*2,l,mid,u,v,gt); upd_inc(id*2 + 1,mid + 1,r,u,v,gt);
st[id] = st[id*2] + st[id*2 + 1];
}
void upd_val(ll id,ll l,ll r,ll u,ll gt){
if (u < l||r < u) return;
if (l == r){
st[id].val = gt; return;
}
ll mid = (l + r)/2; Pass(id);
upd_val(id*2,l,mid,u,gt); upd_val(id*2 + 1,mid + 1,r,u,gt);
st[id] = st[id*2] + st[id*2 + 1];
}
Node Get(ll id,ll l,ll r,ll u,ll v){
if (v < l||r < u) return {0,0,0};
//if (u == 2&&v == 5) cout<<id<<" "<<l<<" "<<r<<"\n";
if (u <= l&&r <= v) return st[id];
ll mid = (l + r)/2; Pass(id);
return Get(id*2,l,mid,u,v) + Get(id*2 + 1,mid + 1,r,u,v);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "test"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
}
cin>>n;
for (ll i = 1;i <= n;i++) cin>>a[i];
for (ll i = 1;i <= n;i++){
while(!S.empty() && a[S.top()] <= a[i]) cand[S.top()].push_back(i),S.pop();
if (!S.empty()) cand[S.top()].push_back(i);
S.push(i);
}
//for (auto i : cand[2]) cout<<i<<" ";
//cout<<Get(1,1,n,1,n).ans;
//return 0;
cin>>Q;
for (ll i = 1;i <= Q;i++) cin>>L>>R,q[L].push_back({R,i});
for (ll i = n;i > 0;i--){
upd_val(1,1,n,i,a[i]);
for (auto j : cand[i]){
upd_inc(1,1,n,2*j - i,n,a[i] + a[j]);
}
for (auto j : q[i]) ans[j.id] = Get(1,1,n,i,j.R).ans;
}
for (ll i = 1;i <= Q;i++) cout<<ans[i]<<"\n";
}
Compilation message
jumps.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization "O2"
|
jumps.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
jumps.cpp: In function 'int main()':
jumps.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
23832 KB |
Output is correct |
2 |
Correct |
16 ms |
23768 KB |
Output is correct |
3 |
Correct |
15 ms |
23756 KB |
Output is correct |
4 |
Correct |
16 ms |
23832 KB |
Output is correct |
5 |
Correct |
16 ms |
23756 KB |
Output is correct |
6 |
Correct |
16 ms |
23788 KB |
Output is correct |
7 |
Correct |
16 ms |
23848 KB |
Output is correct |
8 |
Correct |
17 ms |
23884 KB |
Output is correct |
9 |
Correct |
16 ms |
23760 KB |
Output is correct |
10 |
Correct |
16 ms |
23756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
23832 KB |
Output is correct |
2 |
Correct |
16 ms |
23768 KB |
Output is correct |
3 |
Correct |
15 ms |
23756 KB |
Output is correct |
4 |
Correct |
16 ms |
23832 KB |
Output is correct |
5 |
Correct |
16 ms |
23756 KB |
Output is correct |
6 |
Correct |
16 ms |
23788 KB |
Output is correct |
7 |
Correct |
16 ms |
23848 KB |
Output is correct |
8 |
Correct |
17 ms |
23884 KB |
Output is correct |
9 |
Correct |
16 ms |
23760 KB |
Output is correct |
10 |
Correct |
16 ms |
23756 KB |
Output is correct |
11 |
Correct |
460 ms |
51560 KB |
Output is correct |
12 |
Correct |
465 ms |
51420 KB |
Output is correct |
13 |
Correct |
478 ms |
51532 KB |
Output is correct |
14 |
Correct |
463 ms |
51544 KB |
Output is correct |
15 |
Correct |
464 ms |
51756 KB |
Output is correct |
16 |
Correct |
455 ms |
50972 KB |
Output is correct |
17 |
Correct |
491 ms |
50936 KB |
Output is correct |
18 |
Correct |
464 ms |
50940 KB |
Output is correct |
19 |
Correct |
451 ms |
51464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
324 ms |
51144 KB |
Output is correct |
2 |
Correct |
223 ms |
49732 KB |
Output is correct |
3 |
Correct |
219 ms |
51440 KB |
Output is correct |
4 |
Correct |
325 ms |
50944 KB |
Output is correct |
5 |
Correct |
324 ms |
50988 KB |
Output is correct |
6 |
Correct |
329 ms |
50440 KB |
Output is correct |
7 |
Correct |
317 ms |
50344 KB |
Output is correct |
8 |
Correct |
325 ms |
50184 KB |
Output is correct |
9 |
Correct |
319 ms |
50684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
23832 KB |
Output is correct |
2 |
Correct |
16 ms |
23768 KB |
Output is correct |
3 |
Correct |
15 ms |
23756 KB |
Output is correct |
4 |
Correct |
16 ms |
23832 KB |
Output is correct |
5 |
Correct |
16 ms |
23756 KB |
Output is correct |
6 |
Correct |
16 ms |
23788 KB |
Output is correct |
7 |
Correct |
16 ms |
23848 KB |
Output is correct |
8 |
Correct |
17 ms |
23884 KB |
Output is correct |
9 |
Correct |
16 ms |
23760 KB |
Output is correct |
10 |
Correct |
16 ms |
23756 KB |
Output is correct |
11 |
Correct |
460 ms |
51560 KB |
Output is correct |
12 |
Correct |
465 ms |
51420 KB |
Output is correct |
13 |
Correct |
478 ms |
51532 KB |
Output is correct |
14 |
Correct |
463 ms |
51544 KB |
Output is correct |
15 |
Correct |
464 ms |
51756 KB |
Output is correct |
16 |
Correct |
455 ms |
50972 KB |
Output is correct |
17 |
Correct |
491 ms |
50936 KB |
Output is correct |
18 |
Correct |
464 ms |
50940 KB |
Output is correct |
19 |
Correct |
451 ms |
51464 KB |
Output is correct |
20 |
Correct |
324 ms |
51144 KB |
Output is correct |
21 |
Correct |
223 ms |
49732 KB |
Output is correct |
22 |
Correct |
219 ms |
51440 KB |
Output is correct |
23 |
Correct |
325 ms |
50944 KB |
Output is correct |
24 |
Correct |
324 ms |
50988 KB |
Output is correct |
25 |
Correct |
329 ms |
50440 KB |
Output is correct |
26 |
Correct |
317 ms |
50344 KB |
Output is correct |
27 |
Correct |
325 ms |
50184 KB |
Output is correct |
28 |
Correct |
319 ms |
50684 KB |
Output is correct |
29 |
Correct |
1836 ms |
112392 KB |
Output is correct |
30 |
Correct |
1553 ms |
109260 KB |
Output is correct |
31 |
Correct |
1555 ms |
113244 KB |
Output is correct |
32 |
Correct |
1850 ms |
112208 KB |
Output is correct |
33 |
Correct |
1863 ms |
112272 KB |
Output is correct |
34 |
Correct |
1857 ms |
109944 KB |
Output is correct |
35 |
Correct |
1819 ms |
109600 KB |
Output is correct |
36 |
Correct |
1876 ms |
109596 KB |
Output is correct |
37 |
Correct |
1857 ms |
111084 KB |
Output is correct |
38 |
Correct |
1382 ms |
114820 KB |
Output is correct |
39 |
Correct |
1406 ms |
114836 KB |
Output is correct |
40 |
Correct |
1406 ms |
111576 KB |
Output is correct |
41 |
Correct |
1350 ms |
111028 KB |
Output is correct |
42 |
Correct |
1350 ms |
111140 KB |
Output is correct |
43 |
Correct |
1360 ms |
112864 KB |
Output is correct |
44 |
Correct |
1461 ms |
115392 KB |
Output is correct |
45 |
Correct |
1448 ms |
115108 KB |
Output is correct |
46 |
Correct |
1435 ms |
112016 KB |
Output is correct |
47 |
Correct |
1441 ms |
111628 KB |
Output is correct |
48 |
Correct |
1431 ms |
111640 KB |
Output is correct |
49 |
Correct |
1442 ms |
113728 KB |
Output is correct |
50 |
Correct |
1573 ms |
115616 KB |
Output is correct |
51 |
Correct |
1571 ms |
115496 KB |
Output is correct |
52 |
Correct |
1559 ms |
113112 KB |
Output is correct |
53 |
Correct |
1561 ms |
112484 KB |
Output is correct |
54 |
Correct |
1547 ms |
112656 KB |
Output is correct |
55 |
Correct |
1581 ms |
114228 KB |
Output is correct |