#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz() size()
#define fr first
#define sc second
#define pb push_back
#define er erase
#define in insert
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
///#define cin fin
///#define cout fout
using namespace std;
//ofstream fout("file.out");
const int nmax=1e3+5;
const int mod=1e9+7;
const int mod1=998244353;
int n,a[500005],q,l,r,curr,pop,lazy[2000005];
vector<pair<int,int>>par;
vector<pair<pair<int,int>,int>>que;
vector<pair<int,int>>ans;
pair<int,int>tree[2000005];
stack<int>st;
void createsegtree(int l,int r,int indx){
if(l==r) tree[indx].sc = a[l];
else{
int mid = l+(r-l)/2;
createsegtree(l,mid,2*indx);
createsegtree(mid+1,r,2*indx+1);
tree[indx].sc = max(tree[2*indx].sc,tree[2*indx+1].sc);
}
}
void update(int rangeleft,int rangeright,int val,int lef,int rig,int indx){
if(lazy[indx]!=0){
tree[indx].fr=max(tree[indx].fr,lazy[indx]+tree[indx].sc);
if(lef!=rig){
lazy[2*indx]=max(lazy[2*indx],lazy[indx]);
lazy[2*indx+1]=max(lazy[2*indx+1],lazy[indx]);
}
lazy[indx]=0;
}
if(lef>rangeright || rig<rangeleft) return;
else if(rangeleft<=lef && rangeright>=rig){
tree[indx].fr=max(tree[indx].fr,val+tree[indx].sc);
if(lef!=rig){
lazy[2*indx]=max(lazy[2*indx],val);
lazy[2*indx+1]=max(lazy[2*indx+1],val);
}
}
else{
int mid=lef+(rig-lef)/2;
update(rangeleft,rangeright,val,lef,mid,2*indx);
update(rangeleft,rangeright,val,mid+1,rig,2*indx+1);
tree[indx].fr=max(tree[2*indx].fr,tree[2*indx+1].fr);
}
}
int check(int rangeleft,int rangeright,int lef,int rig,int indx){
if(lazy[indx]!=0){
tree[indx].fr=max(tree[indx].fr,lazy[indx]+tree[indx].sc);
if(lef!=rig){
lazy[2*indx]=max(lazy[2*indx],lazy[indx]);
lazy[2*indx+1]=max(lazy[2*indx+1],lazy[indx]);
}
lazy[indx]=0;
}
if(rangeright<lef || rangeleft>rig) return 0;
else if(rangeleft<=lef && rangeright>=rig){
return tree[indx].fr;
}
else{
int mid=lef+(rig-lef)/2;
return max(check(rangeleft,rangeright,lef,mid,2*indx),check(rangeleft,rangeright,mid+1,rig,2*indx+1));
}
}
int32_t 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];
cin >> q;
for(int i=1;i<=q;i++){
cin >> l >> r;
que.push_back({{l,r},i});
}
sort(all(que));
for(int i=1;i<n;i++){
while(!st.empty() && a[st.top()]<=a[i]){
par.push_back({st.top(),i});
st.pop();
}
if(!st.empty()){
par.push_back({st.top(),i});
}
st.push(i);
}
createsegtree(1,n,1);
sort(all(par));
curr=par.size()-1,pop=que.size()-1;
for(int i=n-2;i>=1;i--){
while(curr>=0 && par[curr].fr==i){
update(2*par[curr].sc-par[curr].fr,n,a[par[curr].fr]+a[par[curr].sc],1,n,1);
curr--;
}
while(pop>=0 && que[pop].fr.fr==i){
ans.push_back({que[pop].sc,check(que[pop].fr.fr,que[pop].fr.sc,1,n,1)});
pop--;
}
}
sort(all(ans));
for(int i=0;i<ans.size();i++){
cout << ans[i].sc << '\n';
}
}
Compilation message
jumps.cpp: In function 'int32_t main()':
jumps.cpp:127:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ans.size();i++){
~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
426 ms |
36740 KB |
Output is correct |
12 |
Correct |
428 ms |
36552 KB |
Output is correct |
13 |
Correct |
454 ms |
36536 KB |
Output is correct |
14 |
Correct |
430 ms |
38380 KB |
Output is correct |
15 |
Correct |
426 ms |
38652 KB |
Output is correct |
16 |
Correct |
430 ms |
36936 KB |
Output is correct |
17 |
Correct |
425 ms |
36460 KB |
Output is correct |
18 |
Correct |
427 ms |
36564 KB |
Output is correct |
19 |
Correct |
428 ms |
37064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
182 ms |
22412 KB |
Output is correct |
2 |
Correct |
103 ms |
19388 KB |
Output is correct |
3 |
Correct |
104 ms |
20772 KB |
Output is correct |
4 |
Correct |
183 ms |
22420 KB |
Output is correct |
5 |
Correct |
232 ms |
22528 KB |
Output is correct |
6 |
Correct |
190 ms |
21692 KB |
Output is correct |
7 |
Correct |
182 ms |
21716 KB |
Output is correct |
8 |
Correct |
179 ms |
21612 KB |
Output is correct |
9 |
Correct |
177 ms |
21984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
426 ms |
36740 KB |
Output is correct |
12 |
Correct |
428 ms |
36552 KB |
Output is correct |
13 |
Correct |
454 ms |
36536 KB |
Output is correct |
14 |
Correct |
430 ms |
38380 KB |
Output is correct |
15 |
Correct |
426 ms |
38652 KB |
Output is correct |
16 |
Correct |
430 ms |
36936 KB |
Output is correct |
17 |
Correct |
425 ms |
36460 KB |
Output is correct |
18 |
Correct |
427 ms |
36564 KB |
Output is correct |
19 |
Correct |
428 ms |
37064 KB |
Output is correct |
20 |
Correct |
182 ms |
22412 KB |
Output is correct |
21 |
Correct |
103 ms |
19388 KB |
Output is correct |
22 |
Correct |
104 ms |
20772 KB |
Output is correct |
23 |
Correct |
183 ms |
22420 KB |
Output is correct |
24 |
Correct |
232 ms |
22528 KB |
Output is correct |
25 |
Correct |
190 ms |
21692 KB |
Output is correct |
26 |
Correct |
182 ms |
21716 KB |
Output is correct |
27 |
Correct |
179 ms |
21612 KB |
Output is correct |
28 |
Correct |
177 ms |
21984 KB |
Output is correct |
29 |
Correct |
1143 ms |
88492 KB |
Output is correct |
30 |
Correct |
927 ms |
80540 KB |
Output is correct |
31 |
Correct |
931 ms |
84808 KB |
Output is correct |
32 |
Correct |
1178 ms |
88544 KB |
Output is correct |
33 |
Correct |
1146 ms |
88496 KB |
Output is correct |
34 |
Correct |
1131 ms |
86064 KB |
Output is correct |
35 |
Correct |
1134 ms |
85812 KB |
Output is correct |
36 |
Correct |
1129 ms |
85936 KB |
Output is correct |
37 |
Correct |
1137 ms |
87412 KB |
Output is correct |
38 |
Correct |
934 ms |
88416 KB |
Output is correct |
39 |
Correct |
940 ms |
88488 KB |
Output is correct |
40 |
Correct |
905 ms |
85124 KB |
Output is correct |
41 |
Correct |
887 ms |
84616 KB |
Output is correct |
42 |
Correct |
896 ms |
84656 KB |
Output is correct |
43 |
Correct |
911 ms |
86288 KB |
Output is correct |
44 |
Correct |
963 ms |
88296 KB |
Output is correct |
45 |
Correct |
963 ms |
88544 KB |
Output is correct |
46 |
Correct |
940 ms |
85264 KB |
Output is correct |
47 |
Correct |
973 ms |
84772 KB |
Output is correct |
48 |
Correct |
958 ms |
84880 KB |
Output is correct |
49 |
Correct |
994 ms |
87004 KB |
Output is correct |
50 |
Correct |
1010 ms |
88416 KB |
Output is correct |
51 |
Correct |
1014 ms |
88428 KB |
Output is correct |
52 |
Correct |
988 ms |
85964 KB |
Output is correct |
53 |
Correct |
979 ms |
85808 KB |
Output is correct |
54 |
Correct |
993 ms |
85604 KB |
Output is correct |
55 |
Correct |
989 ms |
87472 KB |
Output is correct |