#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[500500], L[500500], R[500500], ans[500500];
vector<int> V[500500];
struct Seg{
int tree[1101000], tree2[1101000], lazy[1101000];
void init(int i, int l, int r){
lazy[i] = 0;
if (l==r){
tree[i] = tree2[i] = a[l];
return;
}
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
tree[i] = max(tree[i<<1], tree[i<<1|1]);
tree2[i] = max(tree2[i<<1], tree2[i<<1|1]);
}
void propagate(int i, int l, int r){
tree[i] = max(tree[i], tree2[i] + lazy[i]);
if (l!=r){
lazy[i<<1] = max(lazy[i<<1], lazy[i]);
lazy[i<<1|1] = max(lazy[i<<1|1], lazy[i]);
}
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
lazy[i] = max(lazy[i], x);
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e, x);
update(i<<1|1, m+1, r, s, e, x);
tree[i] = max(tree[i<<1], tree[i<<1|1]);
}
int query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if (r<s || e<l) return 0;
if (s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return max(query(i<<1, l, m, s, e), query(i<<1|1, m+1, r, s, e));
}
}tree;
bool cmp(int i, int j){return L[i] > L[j];}
int main(){
int n;
scanf("%d", &n);
for (int i=1;i<=n;i++) scanf("%d", a+i);
vector<int> st;
for (int i=1;i<=n;i++){
while(!st.empty() && a[st.back()] <= a[i]){
V[st.back()].push_back(i);
st.pop_back();
}
if (!st.empty()) V[st.back()].push_back(i);
st.push_back(i);
}
int q;
vector<int> I;
scanf("%d", &q);
for (int i=1;i<=q;i++){
scanf("%d %d", L+i, R+i);
I.push_back(i);
}
sort(I.begin(), I.end(), cmp);
tree.init(1, 1, n);
int pt = n+1;
for (auto &i:I){
while(L[i] < pt){
--pt;
for (auto &r:V[pt]){
tree.update(1, 1, n, r*2-pt, n, a[pt] + a[r]);
//printf("update (%d %d): %d %d %d\n", pt, r, r*2-pt, n, a[pt] + a[r]);
//if (pt==3 && r==4) printf("%d\n", tree.query(1, 1, n, 5, 5));
}
}
//printf("pt = %d -> %d %d\n", pt, L[i], R[i]);
ans[i] = tree.query(1, 1, n, L[i]+2, R[i]);
}
for (int i=1;i<=q;i++) printf("%d\n", ans[i]);
return 0;
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
jumps.cpp:57:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | for (int i=1;i<=n;i++) scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
jumps.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
jumps.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%d %d", L+i, R+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12072 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
12068 KB |
Output is correct |
4 |
Correct |
6 ms |
12068 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12064 KB |
Output is correct |
7 |
Correct |
7 ms |
12068 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12116 KB |
Output is correct |
10 |
Correct |
6 ms |
12116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12072 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
12068 KB |
Output is correct |
4 |
Correct |
6 ms |
12068 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12064 KB |
Output is correct |
7 |
Correct |
7 ms |
12068 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12116 KB |
Output is correct |
10 |
Correct |
6 ms |
12116 KB |
Output is correct |
11 |
Correct |
348 ms |
29720 KB |
Output is correct |
12 |
Correct |
333 ms |
30004 KB |
Output is correct |
13 |
Correct |
334 ms |
30056 KB |
Output is correct |
14 |
Correct |
344 ms |
30112 KB |
Output is correct |
15 |
Correct |
350 ms |
30112 KB |
Output is correct |
16 |
Correct |
387 ms |
29420 KB |
Output is correct |
17 |
Correct |
354 ms |
29360 KB |
Output is correct |
18 |
Correct |
362 ms |
29328 KB |
Output is correct |
19 |
Correct |
327 ms |
29924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
158 ms |
25572 KB |
Output is correct |
2 |
Correct |
82 ms |
25688 KB |
Output is correct |
3 |
Correct |
86 ms |
26544 KB |
Output is correct |
4 |
Correct |
141 ms |
25892 KB |
Output is correct |
5 |
Correct |
141 ms |
25960 KB |
Output is correct |
6 |
Correct |
151 ms |
25924 KB |
Output is correct |
7 |
Correct |
150 ms |
26484 KB |
Output is correct |
8 |
Correct |
138 ms |
26484 KB |
Output is correct |
9 |
Correct |
136 ms |
26772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12072 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
12068 KB |
Output is correct |
4 |
Correct |
6 ms |
12068 KB |
Output is correct |
5 |
Correct |
6 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
12064 KB |
Output is correct |
7 |
Correct |
7 ms |
12068 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
6 ms |
12116 KB |
Output is correct |
10 |
Correct |
6 ms |
12116 KB |
Output is correct |
11 |
Correct |
348 ms |
29720 KB |
Output is correct |
12 |
Correct |
333 ms |
30004 KB |
Output is correct |
13 |
Correct |
334 ms |
30056 KB |
Output is correct |
14 |
Correct |
344 ms |
30112 KB |
Output is correct |
15 |
Correct |
350 ms |
30112 KB |
Output is correct |
16 |
Correct |
387 ms |
29420 KB |
Output is correct |
17 |
Correct |
354 ms |
29360 KB |
Output is correct |
18 |
Correct |
362 ms |
29328 KB |
Output is correct |
19 |
Correct |
327 ms |
29924 KB |
Output is correct |
20 |
Correct |
158 ms |
25572 KB |
Output is correct |
21 |
Correct |
82 ms |
25688 KB |
Output is correct |
22 |
Correct |
86 ms |
26544 KB |
Output is correct |
23 |
Correct |
141 ms |
25892 KB |
Output is correct |
24 |
Correct |
141 ms |
25960 KB |
Output is correct |
25 |
Correct |
151 ms |
25924 KB |
Output is correct |
26 |
Correct |
150 ms |
26484 KB |
Output is correct |
27 |
Correct |
138 ms |
26484 KB |
Output is correct |
28 |
Correct |
136 ms |
26772 KB |
Output is correct |
29 |
Correct |
948 ms |
66520 KB |
Output is correct |
30 |
Correct |
785 ms |
65888 KB |
Output is correct |
31 |
Correct |
740 ms |
67856 KB |
Output is correct |
32 |
Correct |
907 ms |
66544 KB |
Output is correct |
33 |
Correct |
902 ms |
66416 KB |
Output is correct |
34 |
Correct |
943 ms |
64204 KB |
Output is correct |
35 |
Correct |
919 ms |
63820 KB |
Output is correct |
36 |
Correct |
900 ms |
63808 KB |
Output is correct |
37 |
Correct |
902 ms |
65232 KB |
Output is correct |
38 |
Correct |
778 ms |
66408 KB |
Output is correct |
39 |
Correct |
747 ms |
66420 KB |
Output is correct |
40 |
Correct |
734 ms |
63304 KB |
Output is correct |
41 |
Correct |
739 ms |
62588 KB |
Output is correct |
42 |
Correct |
734 ms |
62684 KB |
Output is correct |
43 |
Correct |
730 ms |
64384 KB |
Output is correct |
44 |
Correct |
779 ms |
66456 KB |
Output is correct |
45 |
Correct |
765 ms |
66460 KB |
Output is correct |
46 |
Correct |
749 ms |
63456 KB |
Output is correct |
47 |
Correct |
743 ms |
63056 KB |
Output is correct |
48 |
Correct |
728 ms |
62932 KB |
Output is correct |
49 |
Correct |
778 ms |
64896 KB |
Output is correct |
50 |
Correct |
846 ms |
66476 KB |
Output is correct |
51 |
Correct |
792 ms |
66504 KB |
Output is correct |
52 |
Correct |
778 ms |
64152 KB |
Output is correct |
53 |
Correct |
780 ms |
63960 KB |
Output is correct |
54 |
Correct |
835 ms |
63748 KB |
Output is correct |
55 |
Correct |
816 ms |
65624 KB |
Output is correct |