#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXN = 5.1e5;
int N;
int A[MAXN];
struct node_t {
int base;
int add;
int best;
node_t() {}
node_t(int base_, int add_, int best_) : base(base_), add(add_), best(best_) {}
node_t operator + (const node_t& o) const {
node_t res;
res.base = max(base, o.base);
res.add = max(add, o.add);
res.best = max({best, o.best, add + o.base});
return res;
}
};
struct seg {
seg* ch[2];
node_t res;
seg() {}
void update() {
assert(ch[0]);
res = ch[0]->res + ch[1]->res;
}
};
seg nodes[MAXN*2];
int NODE;
seg* ROOT;
seg* build(int x = 0, int y = N) {
seg* r = &nodes[NODE++];
if (y - x == 1) {
r->res = node_t(A[x], -INF, -INF);
} else {
int z = (x + y) / 2;
r->ch[0] = build(x, z);
r->ch[1] = build(z, y);
r->update();
}
return r;
}
void update(int k, int v, int x = 0, int y = N, seg* n = ROOT) {
if (y - x == 1) {
n->res.add = max(n->res.add, v);
n->res.best = n->res.base + n->res.add;
} else {
int z = (x + y) / 2;
if (k < z) {
update(k, v, x, z, n->ch[0]);
} else {
update(k, v, z, y, n->ch[1]);
}
n->update();
}
}
node_t query(int l, int r, int x = 0, int y = N, seg* n = ROOT) {
if (l <= x && y <= r) {
return n->res;
} else {
int z = (x + y) / 2;
if (r <= z) {
return query(l, r, x, z, n->ch[0]);
} else if (z <= l) {
return query(l, r, z, y, n->ch[1]);
} else {
return query(l, r, x, z, n->ch[0]) + query(l, r, z, y, n->ch[1]);
}
}
}
vector<int> candidates[MAXN];
vector<array<int, 2>> queries[MAXN];
const int MAXQ = 5.1e5;
int ans[MAXQ];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
vector<int> st;
for (int i = 0; i < N; i++) {
while (!st.empty() && A[st.back()] <= A[i]) {
candidates[st.back()].push_back(i);
st.pop_back();
}
if (!st.empty()) {
candidates[st.back()].push_back(i);
}
st.push_back(i);
}
int Q; cin >> Q;
for (int q = 0; q < Q; q++) {
int l, r; cin >> l >> r; l--;
queries[l].push_back({r, q});
}
ROOT = build();
for (int l = N-1; l >= 0; l--) {
for (int r : candidates[l]) {
int x = 2 * r - l;
if (x < N) {
update(x, A[l] + A[r]);
}
}
for (auto q : queries[l]) {
ans[q[1]] = query(l, q[0]).best;
}
}
for (int q = 0; q < Q; q++) {
cout << ans[q] << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
24312 KB |
Output is correct |
2 |
Correct |
25 ms |
24312 KB |
Output is correct |
3 |
Correct |
25 ms |
24332 KB |
Output is correct |
4 |
Correct |
25 ms |
24312 KB |
Output is correct |
5 |
Correct |
24 ms |
24312 KB |
Output is correct |
6 |
Correct |
25 ms |
24268 KB |
Output is correct |
7 |
Correct |
24 ms |
24312 KB |
Output is correct |
8 |
Correct |
26 ms |
24312 KB |
Output is correct |
9 |
Correct |
27 ms |
24316 KB |
Output is correct |
10 |
Correct |
24 ms |
24284 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
24312 KB |
Output is correct |
2 |
Correct |
25 ms |
24312 KB |
Output is correct |
3 |
Correct |
25 ms |
24332 KB |
Output is correct |
4 |
Correct |
25 ms |
24312 KB |
Output is correct |
5 |
Correct |
24 ms |
24312 KB |
Output is correct |
6 |
Correct |
25 ms |
24268 KB |
Output is correct |
7 |
Correct |
24 ms |
24312 KB |
Output is correct |
8 |
Correct |
26 ms |
24312 KB |
Output is correct |
9 |
Correct |
27 ms |
24316 KB |
Output is correct |
10 |
Correct |
24 ms |
24284 KB |
Output is correct |
11 |
Correct |
356 ms |
42904 KB |
Output is correct |
12 |
Correct |
340 ms |
42744 KB |
Output is correct |
13 |
Correct |
360 ms |
42872 KB |
Output is correct |
14 |
Correct |
362 ms |
42904 KB |
Output is correct |
15 |
Correct |
396 ms |
42988 KB |
Output is correct |
16 |
Correct |
375 ms |
42232 KB |
Output is correct |
17 |
Correct |
357 ms |
42272 KB |
Output is correct |
18 |
Correct |
324 ms |
42104 KB |
Output is correct |
19 |
Correct |
361 ms |
42744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
182 ms |
45920 KB |
Output is correct |
2 |
Correct |
120 ms |
45560 KB |
Output is correct |
3 |
Correct |
124 ms |
46444 KB |
Output is correct |
4 |
Correct |
172 ms |
45816 KB |
Output is correct |
5 |
Correct |
180 ms |
45816 KB |
Output is correct |
6 |
Correct |
168 ms |
45244 KB |
Output is correct |
7 |
Correct |
165 ms |
45176 KB |
Output is correct |
8 |
Correct |
168 ms |
45048 KB |
Output is correct |
9 |
Correct |
169 ms |
45432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
27 ms |
24312 KB |
Output is correct |
2 |
Correct |
25 ms |
24312 KB |
Output is correct |
3 |
Correct |
25 ms |
24332 KB |
Output is correct |
4 |
Correct |
25 ms |
24312 KB |
Output is correct |
5 |
Correct |
24 ms |
24312 KB |
Output is correct |
6 |
Correct |
25 ms |
24268 KB |
Output is correct |
7 |
Correct |
24 ms |
24312 KB |
Output is correct |
8 |
Correct |
26 ms |
24312 KB |
Output is correct |
9 |
Correct |
27 ms |
24316 KB |
Output is correct |
10 |
Correct |
24 ms |
24284 KB |
Output is correct |
11 |
Correct |
356 ms |
42904 KB |
Output is correct |
12 |
Correct |
340 ms |
42744 KB |
Output is correct |
13 |
Correct |
360 ms |
42872 KB |
Output is correct |
14 |
Correct |
362 ms |
42904 KB |
Output is correct |
15 |
Correct |
396 ms |
42988 KB |
Output is correct |
16 |
Correct |
375 ms |
42232 KB |
Output is correct |
17 |
Correct |
357 ms |
42272 KB |
Output is correct |
18 |
Correct |
324 ms |
42104 KB |
Output is correct |
19 |
Correct |
361 ms |
42744 KB |
Output is correct |
20 |
Correct |
182 ms |
45920 KB |
Output is correct |
21 |
Correct |
120 ms |
45560 KB |
Output is correct |
22 |
Correct |
124 ms |
46444 KB |
Output is correct |
23 |
Correct |
172 ms |
45816 KB |
Output is correct |
24 |
Correct |
180 ms |
45816 KB |
Output is correct |
25 |
Correct |
168 ms |
45244 KB |
Output is correct |
26 |
Correct |
165 ms |
45176 KB |
Output is correct |
27 |
Correct |
168 ms |
45048 KB |
Output is correct |
28 |
Correct |
169 ms |
45432 KB |
Output is correct |
29 |
Correct |
1252 ms |
101752 KB |
Output is correct |
30 |
Correct |
1146 ms |
100984 KB |
Output is correct |
31 |
Correct |
1101 ms |
103212 KB |
Output is correct |
32 |
Correct |
1236 ms |
101688 KB |
Output is correct |
33 |
Correct |
1270 ms |
101688 KB |
Output is correct |
34 |
Correct |
1236 ms |
99448 KB |
Output is correct |
35 |
Correct |
1257 ms |
99244 KB |
Output is correct |
36 |
Correct |
1259 ms |
99160 KB |
Output is correct |
37 |
Correct |
1252 ms |
100604 KB |
Output is correct |
38 |
Correct |
754 ms |
107316 KB |
Output is correct |
39 |
Correct |
931 ms |
107512 KB |
Output is correct |
40 |
Correct |
789 ms |
104044 KB |
Output is correct |
41 |
Correct |
731 ms |
103536 KB |
Output is correct |
42 |
Correct |
747 ms |
103512 KB |
Output is correct |
43 |
Correct |
738 ms |
105336 KB |
Output is correct |
44 |
Correct |
843 ms |
106860 KB |
Output is correct |
45 |
Correct |
833 ms |
106872 KB |
Output is correct |
46 |
Correct |
832 ms |
103580 KB |
Output is correct |
47 |
Correct |
825 ms |
103332 KB |
Output is correct |
48 |
Correct |
835 ms |
103312 KB |
Output is correct |
49 |
Correct |
814 ms |
105508 KB |
Output is correct |
50 |
Correct |
1282 ms |
104952 KB |
Output is correct |
51 |
Correct |
1002 ms |
104952 KB |
Output is correct |
52 |
Correct |
939 ms |
102420 KB |
Output is correct |
53 |
Correct |
934 ms |
102224 KB |
Output is correct |
54 |
Correct |
943 ms |
102080 KB |
Output is correct |
55 |
Correct |
1216 ms |
103812 KB |
Output is correct |