#include <bits/stdc++.h>
using namespace std;
const int N = (int) 5e5 + 7;
const int K = 19;
const int INF = (int) 1e9 + 7;
int n;
int q;
int a[N];
int lg[N];
int maxA[K][N];
int nextBigger[N];
int getMaxA(int l, int r) {
if (l > r) {
return -INF;
}
assert(1 <= l && l <= r && r <= n);
int k = lg[r - l + 1];
return max(maxA[k][l], maxA[k][r - (1 << k) + 1]);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
//freopen ("input", "r", stdin);
cin >> n;
for (int i = 2; i <= n; i++) {
lg[i] = lg[i / 2] + 1;
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
maxA[0][i] = a[i];
}
for (int k = 1; (1 << k) <= n; k++) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
maxA[k][i] = max(maxA[k - 1][i], maxA[k - 1][i + (1 << (k - 1))]);
}
}
{ /// just some stack bro
vector<int> stk;
for (int i = n; i >= 1; i--) {
while (!stk.empty() && a[i] >= a[stk.back()]) {
stk.pop_back();
}
nextBigger[i] = (stk.empty() ? (n + 1) : stk.back());
stk.push_back(i);
}
}
cin >> q;
for (int iq = 1; iq <= q; iq++) {
int l, r, best = 0;
cin >> l >> r;
for (int i = l; i <= r; i++) {
/// j is the maximum on the path [i + 1, j]
for (int j = i + 1; j <= r; j = nextBigger[j]) {
int minK = 2 * j - i;
int maxK = r;
best = max(best, a[i] + a[j] + getMaxA(minK, maxK));
}
}
cout << best << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Execution timed out |
4070 ms |
1444 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
15796 KB |
Output is correct |
2 |
Execution timed out |
4078 ms |
16692 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Execution timed out |
4070 ms |
1444 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |