#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
using ll = long long;
using ii = pair<int, int>;
int N, Q, A[500005], ans[500005];
vector<int> ev[500005];
vector<ii> qu[500005];
stack<int> st;
struct node {
node *left, *right;
int S, E, val, r_val, A_val, pv;
node(int _s, int _e) : S(_s), E(_e), r_val(-(int)1e9), pv(-(int)1e9) {
if (S == E) {
A_val = A[S];
return;
}
int M = (S + E) / 2;
left = new node(S, M);
right = new node(M + 1, E);
A_val = max(left->A_val, right->A_val);
}
void prop() {
left->r_val = max(left->r_val, pv + left->A_val);
left->pv = max(left->pv, pv);
right->r_val = max(right->r_val, pv + right->A_val);
right->pv = max(right->pv, pv);
}
void upd(int l, int r, int v) {
if (l > E || r < S) {
return;
}
if (l <= S && E <= r) {
r_val = max(r_val, v + A_val);
pv = max(pv, v);
return;
}
prop();
left->upd(l, r, v);
right->upd(l, r, v);
r_val = max(left->r_val, right->r_val);
}
int qry(int l, int r) {
if (l > E || r < S) {
return -(int)1e9;
}
if (l <= S && E <= r) {
return r_val;
}
prop();
return max(left->qry(l, r), right->qry(l, r));
}
} *root;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
for (int i = N; i >= 1; i--) {
while (!st.empty() && A[st.top()] < A[i]) {
st.pop();
}
if (!st.empty()) {
ev[i].pb(st.top());
}
st.push(i);
}
while (!st.empty()) {
st.pop();
}
for (int i = 1; i <= N; i++) {
while (!st.empty() && A[st.top()] < A[i]) {
st.pop();
}
if (!st.empty()) {
ev[st.top()].pb(i);
}
st.push(i);
}
cin >> Q;
for (int i = 1, L, R; i <= Q; i++) {
cin >> L >> R;
qu[L].eb(R, i);
}
root = new node(1, N);
for (int i = N; i >= 1; i--) {
for (auto b : ev[i]) {
// a = i
root->upd(2 * b - i, N, A[i] + A[b]);
}
for (auto [r, idx] : qu[i]) {
ans[idx] = root->qry(1, r);
}
}
for (int i = 1; i <= Q; i++) {
cout << ans[i] << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
27228 KB |
Output is correct |
2 |
Correct |
6 ms |
27228 KB |
Output is correct |
3 |
Correct |
6 ms |
27256 KB |
Output is correct |
4 |
Correct |
7 ms |
27228 KB |
Output is correct |
5 |
Correct |
6 ms |
27228 KB |
Output is correct |
6 |
Correct |
6 ms |
27296 KB |
Output is correct |
7 |
Correct |
6 ms |
27224 KB |
Output is correct |
8 |
Correct |
6 ms |
27228 KB |
Output is correct |
9 |
Correct |
6 ms |
27228 KB |
Output is correct |
10 |
Correct |
6 ms |
27228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
27228 KB |
Output is correct |
2 |
Correct |
6 ms |
27228 KB |
Output is correct |
3 |
Correct |
6 ms |
27256 KB |
Output is correct |
4 |
Correct |
7 ms |
27228 KB |
Output is correct |
5 |
Correct |
6 ms |
27228 KB |
Output is correct |
6 |
Correct |
6 ms |
27296 KB |
Output is correct |
7 |
Correct |
6 ms |
27224 KB |
Output is correct |
8 |
Correct |
6 ms |
27228 KB |
Output is correct |
9 |
Correct |
6 ms |
27228 KB |
Output is correct |
10 |
Correct |
6 ms |
27228 KB |
Output is correct |
11 |
Correct |
163 ms |
41812 KB |
Output is correct |
12 |
Correct |
164 ms |
41708 KB |
Output is correct |
13 |
Correct |
163 ms |
41736 KB |
Output is correct |
14 |
Correct |
173 ms |
41864 KB |
Output is correct |
15 |
Correct |
162 ms |
41904 KB |
Output is correct |
16 |
Correct |
176 ms |
41300 KB |
Output is correct |
17 |
Correct |
173 ms |
41168 KB |
Output is correct |
18 |
Correct |
180 ms |
41180 KB |
Output is correct |
19 |
Correct |
164 ms |
41988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
110 ms |
53956 KB |
Output is correct |
2 |
Correct |
77 ms |
54324 KB |
Output is correct |
3 |
Correct |
72 ms |
54868 KB |
Output is correct |
4 |
Correct |
111 ms |
54684 KB |
Output is correct |
5 |
Correct |
109 ms |
54684 KB |
Output is correct |
6 |
Correct |
104 ms |
53840 KB |
Output is correct |
7 |
Correct |
111 ms |
53820 KB |
Output is correct |
8 |
Correct |
106 ms |
53920 KB |
Output is correct |
9 |
Correct |
107 ms |
54096 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
27228 KB |
Output is correct |
2 |
Correct |
6 ms |
27228 KB |
Output is correct |
3 |
Correct |
6 ms |
27256 KB |
Output is correct |
4 |
Correct |
7 ms |
27228 KB |
Output is correct |
5 |
Correct |
6 ms |
27228 KB |
Output is correct |
6 |
Correct |
6 ms |
27296 KB |
Output is correct |
7 |
Correct |
6 ms |
27224 KB |
Output is correct |
8 |
Correct |
6 ms |
27228 KB |
Output is correct |
9 |
Correct |
6 ms |
27228 KB |
Output is correct |
10 |
Correct |
6 ms |
27228 KB |
Output is correct |
11 |
Correct |
163 ms |
41812 KB |
Output is correct |
12 |
Correct |
164 ms |
41708 KB |
Output is correct |
13 |
Correct |
163 ms |
41736 KB |
Output is correct |
14 |
Correct |
173 ms |
41864 KB |
Output is correct |
15 |
Correct |
162 ms |
41904 KB |
Output is correct |
16 |
Correct |
176 ms |
41300 KB |
Output is correct |
17 |
Correct |
173 ms |
41168 KB |
Output is correct |
18 |
Correct |
180 ms |
41180 KB |
Output is correct |
19 |
Correct |
164 ms |
41988 KB |
Output is correct |
20 |
Correct |
110 ms |
53956 KB |
Output is correct |
21 |
Correct |
77 ms |
54324 KB |
Output is correct |
22 |
Correct |
72 ms |
54868 KB |
Output is correct |
23 |
Correct |
111 ms |
54684 KB |
Output is correct |
24 |
Correct |
109 ms |
54684 KB |
Output is correct |
25 |
Correct |
104 ms |
53840 KB |
Output is correct |
26 |
Correct |
111 ms |
53820 KB |
Output is correct |
27 |
Correct |
106 ms |
53920 KB |
Output is correct |
28 |
Correct |
107 ms |
54096 KB |
Output is correct |
29 |
Correct |
768 ms |
116876 KB |
Output is correct |
30 |
Correct |
679 ms |
116256 KB |
Output is correct |
31 |
Correct |
652 ms |
118476 KB |
Output is correct |
32 |
Correct |
798 ms |
116736 KB |
Output is correct |
33 |
Correct |
814 ms |
116864 KB |
Output is correct |
34 |
Correct |
760 ms |
114856 KB |
Output is correct |
35 |
Correct |
788 ms |
114088 KB |
Output is correct |
36 |
Correct |
769 ms |
114104 KB |
Output is correct |
37 |
Correct |
749 ms |
115592 KB |
Output is correct |
38 |
Correct |
453 ms |
122552 KB |
Output is correct |
39 |
Correct |
459 ms |
122460 KB |
Output is correct |
40 |
Correct |
445 ms |
119244 KB |
Output is correct |
41 |
Correct |
439 ms |
118680 KB |
Output is correct |
42 |
Correct |
441 ms |
118740 KB |
Output is correct |
43 |
Correct |
446 ms |
120336 KB |
Output is correct |
44 |
Correct |
474 ms |
121828 KB |
Output is correct |
45 |
Correct |
482 ms |
121936 KB |
Output is correct |
46 |
Correct |
470 ms |
118736 KB |
Output is correct |
47 |
Correct |
464 ms |
118356 KB |
Output is correct |
48 |
Correct |
471 ms |
118704 KB |
Output is correct |
49 |
Correct |
476 ms |
120452 KB |
Output is correct |
50 |
Correct |
536 ms |
120084 KB |
Output is correct |
51 |
Correct |
536 ms |
119980 KB |
Output is correct |
52 |
Correct |
531 ms |
117748 KB |
Output is correct |
53 |
Correct |
535 ms |
117276 KB |
Output is correct |
54 |
Correct |
548 ms |
117124 KB |
Output is correct |
55 |
Correct |
541 ms |
118928 KB |
Output is correct |