#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
struct node
{
ll am,bm,sm;
node(ll x=-INF,ll y=-INF):am(x),bm(y),sm(x+y){}
node(ll x,ll y,ll z):am(x),bm(y),sm(z){}
node operator^(node x)
{
return node(max(am,x.am),max(bm,x.bm),max({sm,x.sm,bm+x.am}));
}
};
ll a[500010],b[500010];
struct seg
{
node t[2000010];
seg()
{
fill(t,t+2000010,node());
}
void si(int n,int s,int e,int x)
{
if(s==e)
{
t[n]=node(a[s],b[s]);
return;
}
int m=s+e>>1;
if(x>m)
si(n*2+1,m+1,e,x);
else
si(n*2,s,m,x);
t[n]=t[n*2]^t[n*2+1];
return;
}
node sq(int n,int s,int e,int S,int E)
{
if(s>E||S>e)
return node();
if(S<=s&&e<=E)
return t[n];
int m=s+e>>1;
return sq(n*2,s,m,S,E)^sq(n*2+1,m+1,e,S,E);
}
}st;
vector<pl>qv[500010];
vector<pi>av[500010];
ll ans[500010];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin>>n;
for(int i=0;i++<n;)
cin>>a[i],b[i]=-INF;
vector<int>v;
v.eb(n);
for(int i=n;--i>0;)
{
while(!v.empty())
{
int j=v.back();
if(2*j-i<=n)
qv[i].eb(2*j-i,a[i]+a[j]);
if(a[j]<=a[i])
v.pop_back();
else
break;
}
v.eb(i);
}
cin>>q;
for(int i=0;i<q;i++)
{
int l,r;
cin>>l>>r;
av[l].eb(r,i);
}
for(int i=n;i>0;i--)
{
for(pl&t:qv[i])
if(b[t.fi]<t.se)
b[t.fi]=t.se,st.si(1,1,n,t.fi);
for(pi&t:av[i])
ans[t.se]=st.sq(1,1,n,i+2,t.fi).sm;
}
for(int i=0;i<q;i++)
cout<<ans[i]<<'\n';
cout.flush();
return 0;
}
Compilation message
jumps.cpp: In member function 'void seg::si(int, int, int, int)':
jumps.cpp:42:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=s+e>>1;
~^~
jumps.cpp: In member function 'node seg::sq(int, int, int, int, int)':
jumps.cpp:56:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=s+e>>1;
~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
70820 KB |
Output is correct |
2 |
Correct |
48 ms |
70832 KB |
Output is correct |
3 |
Correct |
49 ms |
70776 KB |
Output is correct |
4 |
Correct |
48 ms |
70776 KB |
Output is correct |
5 |
Correct |
49 ms |
70780 KB |
Output is correct |
6 |
Correct |
57 ms |
70776 KB |
Output is correct |
7 |
Correct |
49 ms |
70776 KB |
Output is correct |
8 |
Correct |
48 ms |
70776 KB |
Output is correct |
9 |
Correct |
49 ms |
70776 KB |
Output is correct |
10 |
Correct |
49 ms |
70904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
70820 KB |
Output is correct |
2 |
Correct |
48 ms |
70832 KB |
Output is correct |
3 |
Correct |
49 ms |
70776 KB |
Output is correct |
4 |
Correct |
48 ms |
70776 KB |
Output is correct |
5 |
Correct |
49 ms |
70780 KB |
Output is correct |
6 |
Correct |
57 ms |
70776 KB |
Output is correct |
7 |
Correct |
49 ms |
70776 KB |
Output is correct |
8 |
Correct |
48 ms |
70776 KB |
Output is correct |
9 |
Correct |
49 ms |
70776 KB |
Output is correct |
10 |
Correct |
49 ms |
70904 KB |
Output is correct |
11 |
Correct |
400 ms |
86492 KB |
Output is correct |
12 |
Correct |
348 ms |
86484 KB |
Output is correct |
13 |
Correct |
401 ms |
86392 KB |
Output is correct |
14 |
Correct |
350 ms |
86392 KB |
Output is correct |
15 |
Correct |
359 ms |
86520 KB |
Output is correct |
16 |
Correct |
378 ms |
85880 KB |
Output is correct |
17 |
Correct |
356 ms |
85880 KB |
Output is correct |
18 |
Correct |
349 ms |
85880 KB |
Output is correct |
19 |
Correct |
392 ms |
86392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
152 ms |
84216 KB |
Output is correct |
2 |
Correct |
118 ms |
81056 KB |
Output is correct |
3 |
Correct |
118 ms |
80248 KB |
Output is correct |
4 |
Correct |
162 ms |
84312 KB |
Output is correct |
5 |
Correct |
167 ms |
84216 KB |
Output is correct |
6 |
Correct |
156 ms |
84216 KB |
Output is correct |
7 |
Correct |
140 ms |
84216 KB |
Output is correct |
8 |
Correct |
143 ms |
84220 KB |
Output is correct |
9 |
Correct |
159 ms |
84216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
70820 KB |
Output is correct |
2 |
Correct |
48 ms |
70832 KB |
Output is correct |
3 |
Correct |
49 ms |
70776 KB |
Output is correct |
4 |
Correct |
48 ms |
70776 KB |
Output is correct |
5 |
Correct |
49 ms |
70780 KB |
Output is correct |
6 |
Correct |
57 ms |
70776 KB |
Output is correct |
7 |
Correct |
49 ms |
70776 KB |
Output is correct |
8 |
Correct |
48 ms |
70776 KB |
Output is correct |
9 |
Correct |
49 ms |
70776 KB |
Output is correct |
10 |
Correct |
49 ms |
70904 KB |
Output is correct |
11 |
Correct |
400 ms |
86492 KB |
Output is correct |
12 |
Correct |
348 ms |
86484 KB |
Output is correct |
13 |
Correct |
401 ms |
86392 KB |
Output is correct |
14 |
Correct |
350 ms |
86392 KB |
Output is correct |
15 |
Correct |
359 ms |
86520 KB |
Output is correct |
16 |
Correct |
378 ms |
85880 KB |
Output is correct |
17 |
Correct |
356 ms |
85880 KB |
Output is correct |
18 |
Correct |
349 ms |
85880 KB |
Output is correct |
19 |
Correct |
392 ms |
86392 KB |
Output is correct |
20 |
Correct |
152 ms |
84216 KB |
Output is correct |
21 |
Correct |
118 ms |
81056 KB |
Output is correct |
22 |
Correct |
118 ms |
80248 KB |
Output is correct |
23 |
Correct |
162 ms |
84312 KB |
Output is correct |
24 |
Correct |
167 ms |
84216 KB |
Output is correct |
25 |
Correct |
156 ms |
84216 KB |
Output is correct |
26 |
Correct |
140 ms |
84216 KB |
Output is correct |
27 |
Correct |
143 ms |
84220 KB |
Output is correct |
28 |
Correct |
159 ms |
84216 KB |
Output is correct |
29 |
Correct |
1221 ms |
123280 KB |
Output is correct |
30 |
Correct |
924 ms |
115092 KB |
Output is correct |
31 |
Correct |
943 ms |
113144 KB |
Output is correct |
32 |
Correct |
1033 ms |
123256 KB |
Output is correct |
33 |
Correct |
1053 ms |
123256 KB |
Output is correct |
34 |
Correct |
1051 ms |
122524 KB |
Output is correct |
35 |
Correct |
1037 ms |
122616 KB |
Output is correct |
36 |
Correct |
1053 ms |
122464 KB |
Output is correct |
37 |
Correct |
1035 ms |
123068 KB |
Output is correct |
38 |
Correct |
719 ms |
129016 KB |
Output is correct |
39 |
Correct |
724 ms |
128888 KB |
Output is correct |
40 |
Correct |
674 ms |
127100 KB |
Output is correct |
41 |
Correct |
670 ms |
129784 KB |
Output is correct |
42 |
Correct |
705 ms |
135964 KB |
Output is correct |
43 |
Correct |
709 ms |
137700 KB |
Output is correct |
44 |
Correct |
762 ms |
138120 KB |
Output is correct |
45 |
Correct |
763 ms |
138092 KB |
Output is correct |
46 |
Correct |
745 ms |
136052 KB |
Output is correct |
47 |
Correct |
721 ms |
135592 KB |
Output is correct |
48 |
Correct |
749 ms |
135772 KB |
Output is correct |
49 |
Correct |
756 ms |
137664 KB |
Output is correct |
50 |
Correct |
863 ms |
136160 KB |
Output is correct |
51 |
Correct |
841 ms |
136108 KB |
Output is correct |
52 |
Correct |
812 ms |
135164 KB |
Output is correct |
53 |
Correct |
800 ms |
134480 KB |
Output is correct |
54 |
Correct |
807 ms |
134576 KB |
Output is correct |
55 |
Correct |
822 ms |
136284 KB |
Output is correct |