#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
int n,q;
int a[500005];
int ans[500005];
vector<ii> good[500005];
vector<ii> query[500005];
struct node{
int s,e,m,ab,c,abc;
node *l, *r;
node (int _s, int _e) : s(_s), e(_e){
m = (s+e)/2;
ab = c = abc = 0;
if (s != e){
l = new node(s,m);
r = new node(m+1,e);
ab = max(l->ab,r->ab);
c = max(l->c,r->c);
abc = max(l->ab+r->c,max(l->abc,r->abc));
}
else{
c = a[s];
}
}
void up(int x, int nv){
if (s == e){
ab = max(ab,nv);
abc = nv+c;
return;
}
if (x > m) r->up(x,nv);
else l->up(x,nv);
ab = max(l->ab,r->ab);
c = max(l->c,r->c);
abc = max(l->ab+r->c,max(l->abc,r->abc));
}
iii query(int qs, int qe){
//printf("segment tree <%d,%d>\n",qs,qe);
if (qs == s && qe == e){
return iii(ab,c,abc);
}
else if (qs > m) return r->query(qs,qe);
else if (qe <= m) return l->query(qs,qe);
else{
iii L = l->query(qs,m);
iii R = r->query(m+1,qe);
int AB = max(get<0>(L),get<0>(R));
int C = max(get<1>(L),get<1>(R));
int ABC = max(get<0>(L)+get<1>(R),max(get<2>(L),get<2>(R)));
return {AB,C,ABC};
}
}
} *root;
stack<ii> s;
int main(){
scanf("%d",&n);
for (int i = 1; i <= n; i++){
scanf("%d",&a[i]);
}
for (int i = 1; i <= n; i++){
while (s.size() && s.top().second <= a[i]){
int A = s.top().first;
int C = i-A+i;
int V = a[A] + a[i];
//printf("stack %d %d\n",A,i);
if (C <= n) good[A].push_back({C,V});
s.pop();
}
if (s.size()){
int A = s.top().first;
int C = i-A+i;
int V = a[A] + a[i];
//printf("stack %d %d\n",A,i);
if (C <= n) good[A].push_back({C,V});
}
s.push({i,a[i]});
}
scanf("%d",&q);
for (int i = 0; i < q; i++){
int l,r;
scanf("%d%d",&l,&r);
query[l].push_back({r,i});
}
root = new node(1,n);
for (int i = n; i >= 1; i--){
for (auto x : good[i]){
//printf("%d: updating %d with %d\n",i,x.first,x.second);
root->up(x.first,x.second);
}
for (auto x : query[i]){
//printf("%d: query %d <%d,%d>\n",i,x.second,i,x.first);
ans[x.second] = get<2>(root->query(i,x.first));
}
}
for (int i = 0; i < q; i++){
printf("%d\n",ans[i]);
}
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
jumps.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
~~~~~^~~~~~~~~~~~
jumps.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
jumps.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&l,&r);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
23808 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
23808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
23808 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
23808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
52600 KB |
Output is correct |
| 2 |
Correct |
114 ms |
51448 KB |
Output is correct |
| 3 |
Correct |
114 ms |
53112 KB |
Output is correct |
| 4 |
Correct |
172 ms |
52600 KB |
Output is correct |
| 5 |
Correct |
168 ms |
52600 KB |
Output is correct |
| 6 |
Correct |
167 ms |
52036 KB |
Output is correct |
| 7 |
Correct |
163 ms |
51928 KB |
Output is correct |
| 8 |
Correct |
157 ms |
51832 KB |
Output is correct |
| 9 |
Correct |
167 ms |
52216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
23808 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
23808 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
