#include <bits/stdc++.h>
using namespace std;
const int N = 505050;
const int B = 21;
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^2 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 = 0; j < p.size(); j++) {
int x = p[i], y = p[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 = 0; j < p.size(); j++) {
| ~~^~~~~~~~~~
jumps.cpp:60:62: 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 = 0; j < p.size(); j++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
6 ms |
340 KB |
Output is correct |
| 3 |
Correct |
8 ms |
212 KB |
Output is correct |
| 4 |
Correct |
5 ms |
328 KB |
Output is correct |
| 5 |
Correct |
8 ms |
340 KB |
Output is correct |
| 6 |
Correct |
7 ms |
340 KB |
Output is correct |
| 7 |
Correct |
6 ms |
212 KB |
Output is correct |
| 8 |
Correct |
6 ms |
212 KB |
Output is correct |
| 9 |
Correct |
6 ms |
328 KB |
Output is correct |
| 10 |
Correct |
5 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
6 ms |
340 KB |
Output is correct |
| 3 |
Correct |
8 ms |
212 KB |
Output is correct |
| 4 |
Correct |
5 ms |
328 KB |
Output is correct |
| 5 |
Correct |
8 ms |
340 KB |
Output is correct |
| 6 |
Correct |
7 ms |
340 KB |
Output is correct |
| 7 |
Correct |
6 ms |
212 KB |
Output is correct |
| 8 |
Correct |
6 ms |
212 KB |
Output is correct |
| 9 |
Correct |
6 ms |
328 KB |
Output is correct |
| 10 |
Correct |
5 ms |
340 KB |
Output is correct |
| 11 |
Execution timed out |
4082 ms |
1036 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
6992 KB |
Output is correct |
| 2 |
Correct |
26 ms |
7148 KB |
Output is correct |
| 3 |
Correct |
34 ms |
6980 KB |
Output is correct |
| 4 |
Correct |
39 ms |
7028 KB |
Output is correct |
| 5 |
Correct |
38 ms |
7004 KB |
Output is correct |
| 6 |
Incorrect |
46 ms |
6400 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
6 ms |
340 KB |
Output is correct |
| 3 |
Correct |
8 ms |
212 KB |
Output is correct |
| 4 |
Correct |
5 ms |
328 KB |
Output is correct |
| 5 |
Correct |
8 ms |
340 KB |
Output is correct |
| 6 |
Correct |
7 ms |
340 KB |
Output is correct |
| 7 |
Correct |
6 ms |
212 KB |
Output is correct |
| 8 |
Correct |
6 ms |
212 KB |
Output is correct |
| 9 |
Correct |
6 ms |
328 KB |
Output is correct |
| 10 |
Correct |
5 ms |
340 KB |
Output is correct |
| 11 |
Execution timed out |
4082 ms |
1036 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
