#include <bits/stdc++.h>
using namespace std;
const int N = 505050;
const int B = 20;
int n, q, a[N];
struct SEG {
int tree[N * 4];
void init(int l, int r, int x) {
if (l == r) {
tree[x] = a[l];
return;
}
int m = (l + r) / 2;
init(l, m, 2 * x);
init(m + 1, r, 2 * x + 1);
tree[x] = max(tree[2 * x], tree[2 * x + 1]);
}
int query(int a, int b, int l, int r, int x) {
if (b < l || a > r)
return 0;
if (a <= l && r <= b)
return tree[x];
int m = (l + r) / 2;
return max(query(a, b, l, m, 2 * x), query(a, b, m + 1, r, 2 * x + 1));
}
} t1;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
t1.init(1, n, 1);
cin >> q;
while (q--) { // O(n log n + log^3 n) per each query
int l, r; cin >> l >> r;
vector<pair<int, int>> v;
for (int i = l; i <= r; i++)
v.push_back({a[i], i});
sort(v.rbegin(), v.rend());
// largest log_2 n elements are critical
vector<int> p;
for (int i = 0; i < min(B, (int)v.size()); i++)
p.push_back(v[i].second);
sort(p.begin(), p.end());
int ans = 0;
// use three
for (int i = 0; i < p.size(); i++) for (int j = i + 1; j < p.size(); j++) for (int k = j + 1; k < p.size(); k++) {
if (p[j] - p[i] <= p[k] - p[j])
ans = max(ans, a[p[i]] + a[p[j]] + a[p[k]]);
}
// use one or two
for (int i = 0; i < p.size(); i++) for (int j = l; j <= r; j++) {
int x = p[i], y = j;
if (x == y)
continue;
if (x > y)
swap(x, y);
int d = y - x;
// left
ans = max(ans, a[x] + a[y] + t1.query(max(x - d, l), x - 1, 1, n, 1));
// middle
if (x < x + d / 2)
ans = max(ans, a[x] + a[y] + t1.query(x + 1, x + d / 2, 1, n, 1));
// right
if (y + d <= r)
ans = max(ans, a[x] + a[y] + t1.query(y + d, r, 1, n, 1));
}
cout << ans << '\n';
}
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 0; i < p.size(); i++) for (int j = i + 1; j < p.size(); j++) for (int k = j + 1; k < p.size(); k++) {
| ~~^~~~~~~~~~
jumps.cpp:55:66: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 0; i < p.size(); i++) for (int j = i + 1; j < p.size(); j++) for (int k = j + 1; k < p.size(); k++) {
| ~~^~~~~~~~~~
jumps.cpp:55:105: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for (int i = 0; i < p.size(); i++) for (int j = i + 1; j < p.size(); j++) for (int k = j + 1; k < p.size(); k++) {
| ~~^~~~~~~~~~
jumps.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int i = 0; i < p.size(); i++) for (int j = l; j <= r; j++) {
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
12 ms |
340 KB |
Output is correct |
3 |
Correct |
10 ms |
340 KB |
Output is correct |
4 |
Correct |
9 ms |
336 KB |
Output is correct |
5 |
Correct |
9 ms |
332 KB |
Output is correct |
6 |
Correct |
10 ms |
324 KB |
Output is correct |
7 |
Correct |
13 ms |
336 KB |
Output is correct |
8 |
Correct |
10 ms |
340 KB |
Output is correct |
9 |
Correct |
12 ms |
340 KB |
Output is correct |
10 |
Correct |
12 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
12 ms |
340 KB |
Output is correct |
3 |
Correct |
10 ms |
340 KB |
Output is correct |
4 |
Correct |
9 ms |
336 KB |
Output is correct |
5 |
Correct |
9 ms |
332 KB |
Output is correct |
6 |
Correct |
10 ms |
324 KB |
Output is correct |
7 |
Correct |
13 ms |
336 KB |
Output is correct |
8 |
Correct |
10 ms |
340 KB |
Output is correct |
9 |
Correct |
12 ms |
340 KB |
Output is correct |
10 |
Correct |
12 ms |
340 KB |
Output is correct |
11 |
Execution timed out |
4066 ms |
748 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1356 ms |
6984 KB |
Output is correct |
2 |
Correct |
1261 ms |
6984 KB |
Output is correct |
3 |
Correct |
1020 ms |
6984 KB |
Output is correct |
4 |
Correct |
1251 ms |
7036 KB |
Output is correct |
5 |
Correct |
1300 ms |
6988 KB |
Output is correct |
6 |
Correct |
1306 ms |
6344 KB |
Output is correct |
7 |
Correct |
1370 ms |
6256 KB |
Output is correct |
8 |
Correct |
1420 ms |
6336 KB |
Output is correct |
9 |
Correct |
1393 ms |
6636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
12 ms |
340 KB |
Output is correct |
3 |
Correct |
10 ms |
340 KB |
Output is correct |
4 |
Correct |
9 ms |
336 KB |
Output is correct |
5 |
Correct |
9 ms |
332 KB |
Output is correct |
6 |
Correct |
10 ms |
324 KB |
Output is correct |
7 |
Correct |
13 ms |
336 KB |
Output is correct |
8 |
Correct |
10 ms |
340 KB |
Output is correct |
9 |
Correct |
12 ms |
340 KB |
Output is correct |
10 |
Correct |
12 ms |
340 KB |
Output is correct |
11 |
Execution timed out |
4066 ms |
748 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |