#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e14;
const int N = 5e5 + 5;
struct node {
ll A, B, BA;
node(ll _A = -INF, ll _B = -INF, ll _BA = -INF) {
A = _A, B = _B, BA = _BA;
}
};
node tree[4 * N];
int n, q;
ll a[N];
vector <int> r[N];
vector <pair <int, int>> Q[N];
node merge(node x, node y) {
return node(max(x.A, y.A), max(x.B, y.B), max({x.BA, y.BA, x.B + y.A}));
}
void update(int node, int s, int e, int idx, ll val, bool flag) {
if(idx < s or idx > e) return;
if(s == e) {
if(flag) tree[node].B = max(tree[node].B, val);
else tree[node].A = max(tree[node].A, val);
tree[node].BA = max(-INF, tree[node].A + tree[node].B);
return;
}
int mid = (s + e) / 2;
update(2 * node, s, mid, idx, val, flag);
update(2 * node + 1, mid + 1, e, idx, val, flag);
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
node query(int node, int s, int e, int l, int r) {
if(l > e or r < s) return {-INF, -INF, -INF};
if(s >= l and e <= r) {
return tree[node];
}
int mid = (s + e) / 2;
return merge(query(2 * node, s, mid, l, r), query(2 * node + 1, mid + 1, e, l, r));
}
int main() {
scanf("%d", &n);
stack <ll> s;
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
while(!s.empty() and a[s.top()] <= a[i]) {
r[s.top()].push_back(i);
s.pop();
}
if(!s.empty()) {
r[s.top()].push_back(i);
}
s.push(i);
update(1, 1, n, i, a[i], 0);
}
scanf("%d", &q);
for(int i = 0; i < q; i++) {
int l, r; scanf("%d %d", &l, &r);
Q[l].push_back({r, i});
}
vector <ll> ans(q);
for(int i = n; i >= 1; i--) {
for(auto p : r[i]) {
if(p + p - i <= n) {
update(1, 1, n, p + p - i, a[p] + a[i], 1);
}
}
for(auto p : Q[i]) {
ans[p.second] = query(1, 1, n, i, p.first).BA;
}
}
for(int i = 0; i < q; i++) {
printf("%lld\n", ans[i]);
}
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
jumps.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &a[i]);
~~~~~^~~~~~~~~~~~~~~
jumps.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
jumps.cpp:68:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int l, r; scanf("%d %d", &l, &r);
~~~~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
70776 KB |
Output is correct |
2 |
Correct |
61 ms |
70776 KB |
Output is correct |
3 |
Correct |
61 ms |
70776 KB |
Output is correct |
4 |
Correct |
60 ms |
70776 KB |
Output is correct |
5 |
Correct |
61 ms |
70776 KB |
Output is correct |
6 |
Correct |
62 ms |
71016 KB |
Output is correct |
7 |
Correct |
61 ms |
70712 KB |
Output is correct |
8 |
Correct |
61 ms |
70748 KB |
Output is correct |
9 |
Correct |
61 ms |
70776 KB |
Output is correct |
10 |
Correct |
66 ms |
70776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
70776 KB |
Output is correct |
2 |
Correct |
61 ms |
70776 KB |
Output is correct |
3 |
Correct |
61 ms |
70776 KB |
Output is correct |
4 |
Correct |
60 ms |
70776 KB |
Output is correct |
5 |
Correct |
61 ms |
70776 KB |
Output is correct |
6 |
Correct |
62 ms |
71016 KB |
Output is correct |
7 |
Correct |
61 ms |
70712 KB |
Output is correct |
8 |
Correct |
61 ms |
70748 KB |
Output is correct |
9 |
Correct |
61 ms |
70776 KB |
Output is correct |
10 |
Correct |
66 ms |
70776 KB |
Output is correct |
11 |
Correct |
495 ms |
91072 KB |
Output is correct |
12 |
Correct |
486 ms |
91000 KB |
Output is correct |
13 |
Correct |
502 ms |
91092 KB |
Output is correct |
14 |
Correct |
499 ms |
91012 KB |
Output is correct |
15 |
Correct |
580 ms |
90940 KB |
Output is correct |
16 |
Correct |
509 ms |
90408 KB |
Output is correct |
17 |
Correct |
494 ms |
90360 KB |
Output is correct |
18 |
Correct |
590 ms |
90352 KB |
Output is correct |
19 |
Correct |
500 ms |
90872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
306 ms |
80504 KB |
Output is correct |
2 |
Correct |
220 ms |
80440 KB |
Output is correct |
3 |
Correct |
226 ms |
81528 KB |
Output is correct |
4 |
Correct |
315 ms |
80760 KB |
Output is correct |
5 |
Correct |
311 ms |
80584 KB |
Output is correct |
6 |
Correct |
299 ms |
79864 KB |
Output is correct |
7 |
Correct |
294 ms |
79924 KB |
Output is correct |
8 |
Correct |
290 ms |
79736 KB |
Output is correct |
9 |
Correct |
296 ms |
80120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
70776 KB |
Output is correct |
2 |
Correct |
61 ms |
70776 KB |
Output is correct |
3 |
Correct |
61 ms |
70776 KB |
Output is correct |
4 |
Correct |
60 ms |
70776 KB |
Output is correct |
5 |
Correct |
61 ms |
70776 KB |
Output is correct |
6 |
Correct |
62 ms |
71016 KB |
Output is correct |
7 |
Correct |
61 ms |
70712 KB |
Output is correct |
8 |
Correct |
61 ms |
70748 KB |
Output is correct |
9 |
Correct |
61 ms |
70776 KB |
Output is correct |
10 |
Correct |
66 ms |
70776 KB |
Output is correct |
11 |
Correct |
495 ms |
91072 KB |
Output is correct |
12 |
Correct |
486 ms |
91000 KB |
Output is correct |
13 |
Correct |
502 ms |
91092 KB |
Output is correct |
14 |
Correct |
499 ms |
91012 KB |
Output is correct |
15 |
Correct |
580 ms |
90940 KB |
Output is correct |
16 |
Correct |
509 ms |
90408 KB |
Output is correct |
17 |
Correct |
494 ms |
90360 KB |
Output is correct |
18 |
Correct |
590 ms |
90352 KB |
Output is correct |
19 |
Correct |
500 ms |
90872 KB |
Output is correct |
20 |
Correct |
306 ms |
80504 KB |
Output is correct |
21 |
Correct |
220 ms |
80440 KB |
Output is correct |
22 |
Correct |
226 ms |
81528 KB |
Output is correct |
23 |
Correct |
315 ms |
80760 KB |
Output is correct |
24 |
Correct |
311 ms |
80584 KB |
Output is correct |
25 |
Correct |
299 ms |
79864 KB |
Output is correct |
26 |
Correct |
294 ms |
79924 KB |
Output is correct |
27 |
Correct |
290 ms |
79736 KB |
Output is correct |
28 |
Correct |
296 ms |
80120 KB |
Output is correct |
29 |
Correct |
1648 ms |
120760 KB |
Output is correct |
30 |
Correct |
1380 ms |
120212 KB |
Output is correct |
31 |
Correct |
1487 ms |
124264 KB |
Output is correct |
32 |
Correct |
1584 ms |
120932 KB |
Output is correct |
33 |
Correct |
1623 ms |
120992 KB |
Output is correct |
34 |
Correct |
1561 ms |
118532 KB |
Output is correct |
35 |
Correct |
1557 ms |
118460 KB |
Output is correct |
36 |
Correct |
1568 ms |
118360 KB |
Output is correct |
37 |
Correct |
1576 ms |
119696 KB |
Output is correct |
38 |
Correct |
1284 ms |
126540 KB |
Output is correct |
39 |
Correct |
1220 ms |
126520 KB |
Output is correct |
40 |
Correct |
1254 ms |
123392 KB |
Output is correct |
41 |
Correct |
1130 ms |
122792 KB |
Output is correct |
42 |
Correct |
1141 ms |
122828 KB |
Output is correct |
43 |
Correct |
1201 ms |
124388 KB |
Output is correct |
44 |
Correct |
1271 ms |
125916 KB |
Output is correct |
45 |
Correct |
1273 ms |
125844 KB |
Output is correct |
46 |
Correct |
1310 ms |
122692 KB |
Output is correct |
47 |
Correct |
1216 ms |
122376 KB |
Output is correct |
48 |
Correct |
1244 ms |
122488 KB |
Output is correct |
49 |
Correct |
1226 ms |
124532 KB |
Output is correct |
50 |
Correct |
1355 ms |
124104 KB |
Output is correct |
51 |
Correct |
1346 ms |
124028 KB |
Output is correct |
52 |
Correct |
1355 ms |
121592 KB |
Output is correct |
53 |
Correct |
1335 ms |
121156 KB |
Output is correct |
54 |
Correct |
1422 ms |
121244 KB |
Output is correct |
55 |
Correct |
1355 ms |
123000 KB |
Output is correct |