#include <bits/stdc++.h>
using namespace std;
struct node
{
int s, e, m, v;
node *l, *r;
node(int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), v(-1)
{
if (s != e)
l = new node(s, m),
r = new node(m + 1, e);
}
void upd(int n, int x)
{
if (s == e)
{
v = x;
return;
}
if (n <= m)
l->upd(n, x);
else
r->upd(n, x);
v = max(l->v, r->v);
}
int qry(int a, int b)
{
if (b < s || a > e)
return -1;
if (a <= s && b >= e)
return v;
return max(l->qry(a, b), r->qry(a, b));
}
} *root;
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, x, Q, l, r;
cin >> N;
vector<int> stiff(N + 5, -1);
root = new node(0, N + 5);
for (int i = 0; i < N; i++)
{
cin >> x;
root->upd(i, x);
stiff[i] = x;
}
vector<vector<int>> precomp(N + 5, vector<int>(N + 5, -1)), prefix(N + 5, vector<int>(N + 5, -1)), ans(N, vector<int>(N + 5, -1));
for (int i = 0; i < N; i++)
{
for (int j = i + 2; j < N; j++)
{
precomp[i][j] = stiff[i] + stiff[j] + root->qry(i + 1, (i + j) / 2);
}
}
for (int i = N - 1; i >= 0; i--)
{
for (int j = i + 2; j < N; j++)
{
prefix[i][j] = max(prefix[i + 1][j], precomp[i][j]);
}
}
for (int i = 0; i < N; i++)
{
for (int j = i + 2; j < N; j++)
{
ans[i][j] = max(ans[i][j - 1], prefix[i][j]);
}
}
cin >> Q;
for (int i = 0; i < Q; i++)
{
cin >> l >> r;
l--, r--;
cout << ans[l][r] << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1291 ms |
304976 KB |
Output is correct |
12 |
Correct |
1293 ms |
304980 KB |
Output is correct |
13 |
Correct |
1286 ms |
305096 KB |
Output is correct |
14 |
Correct |
1313 ms |
305340 KB |
Output is correct |
15 |
Correct |
1278 ms |
305152 KB |
Output is correct |
16 |
Correct |
1306 ms |
304396 KB |
Output is correct |
17 |
Correct |
1292 ms |
304312 KB |
Output is correct |
18 |
Correct |
1325 ms |
304316 KB |
Output is correct |
19 |
Correct |
1274 ms |
305084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
248 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1291 ms |
304976 KB |
Output is correct |
12 |
Correct |
1293 ms |
304980 KB |
Output is correct |
13 |
Correct |
1286 ms |
305096 KB |
Output is correct |
14 |
Correct |
1313 ms |
305340 KB |
Output is correct |
15 |
Correct |
1278 ms |
305152 KB |
Output is correct |
16 |
Correct |
1306 ms |
304396 KB |
Output is correct |
17 |
Correct |
1292 ms |
304312 KB |
Output is correct |
18 |
Correct |
1325 ms |
304316 KB |
Output is correct |
19 |
Correct |
1274 ms |
305084 KB |
Output is correct |
20 |
Runtime error |
248 ms |
524288 KB |
Execution killed with signal 9 |
21 |
Halted |
0 ms |
0 KB |
- |