#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]);
}
struct Offer {
int value;
int lft;
int rgh;
};
struct Question {
int l;
int r;
int ind;
};
bool operator < (Offer a, Offer b) {
return a.lft > b.lft;
}
vector<Question> questionsAt[N];
int best[N];
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);
}
}
vector<Offer> offers;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= min(n, nextBigger[i]); j = nextBigger[j]) {
if (2 * j - i <= n) {
offers.push_back({a[i] + a[j], i, 2 * j - i});
}
}
}
sort(offers.begin(), offers.end());
cin >> q;
vector<int> solPrint(q, -1);
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
questionsAt[l].push_back({l, r, i});
}
for (int i = 1; i <= n; i++) {
best[i] = -INF;
}
int last = -1;
for (int l = n; l >= 1; l--) {
while (last + 1 < (int) offers.size() && l <= offers[last + 1].lft) {
last++;
for (int r = offers[last].rgh; r <= n; r++) {
best[r] = max(best[r], offers[last].value + a[r]);
}
}
for (auto &it : questionsAt[l]) {
int r = it.r, ind = it.ind, maximum = 0;
for (int j = l; j <= r; j++) {
maximum = max(maximum, best[j]);
}
solPrint[ind] = maximum;
}
}
for (auto &x : solPrint) {
assert(x != -1);
cout << x << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11980 KB |
Output is correct |
2 |
Correct |
6 ms |
12108 KB |
Output is correct |
3 |
Correct |
6 ms |
12108 KB |
Output is correct |
4 |
Correct |
7 ms |
12108 KB |
Output is correct |
5 |
Correct |
6 ms |
12108 KB |
Output is correct |
6 |
Correct |
7 ms |
12108 KB |
Output is correct |
7 |
Correct |
6 ms |
12108 KB |
Output is correct |
8 |
Correct |
6 ms |
12108 KB |
Output is correct |
9 |
Correct |
6 ms |
12108 KB |
Output is correct |
10 |
Correct |
6 ms |
12108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11980 KB |
Output is correct |
2 |
Correct |
6 ms |
12108 KB |
Output is correct |
3 |
Correct |
6 ms |
12108 KB |
Output is correct |
4 |
Correct |
7 ms |
12108 KB |
Output is correct |
5 |
Correct |
6 ms |
12108 KB |
Output is correct |
6 |
Correct |
7 ms |
12108 KB |
Output is correct |
7 |
Correct |
6 ms |
12108 KB |
Output is correct |
8 |
Correct |
6 ms |
12108 KB |
Output is correct |
9 |
Correct |
6 ms |
12108 KB |
Output is correct |
10 |
Correct |
6 ms |
12108 KB |
Output is correct |
11 |
Correct |
995 ms |
29740 KB |
Output is correct |
12 |
Correct |
967 ms |
34180 KB |
Output is correct |
13 |
Correct |
1012 ms |
34188 KB |
Output is correct |
14 |
Correct |
973 ms |
34344 KB |
Output is correct |
15 |
Correct |
966 ms |
34388 KB |
Output is correct |
16 |
Correct |
963 ms |
33752 KB |
Output is correct |
17 |
Correct |
971 ms |
33696 KB |
Output is correct |
18 |
Correct |
976 ms |
33568 KB |
Output is correct |
19 |
Correct |
962 ms |
34240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4081 ms |
33800 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11980 KB |
Output is correct |
2 |
Correct |
6 ms |
12108 KB |
Output is correct |
3 |
Correct |
6 ms |
12108 KB |
Output is correct |
4 |
Correct |
7 ms |
12108 KB |
Output is correct |
5 |
Correct |
6 ms |
12108 KB |
Output is correct |
6 |
Correct |
7 ms |
12108 KB |
Output is correct |
7 |
Correct |
6 ms |
12108 KB |
Output is correct |
8 |
Correct |
6 ms |
12108 KB |
Output is correct |
9 |
Correct |
6 ms |
12108 KB |
Output is correct |
10 |
Correct |
6 ms |
12108 KB |
Output is correct |
11 |
Correct |
995 ms |
29740 KB |
Output is correct |
12 |
Correct |
967 ms |
34180 KB |
Output is correct |
13 |
Correct |
1012 ms |
34188 KB |
Output is correct |
14 |
Correct |
973 ms |
34344 KB |
Output is correct |
15 |
Correct |
966 ms |
34388 KB |
Output is correct |
16 |
Correct |
963 ms |
33752 KB |
Output is correct |
17 |
Correct |
971 ms |
33696 KB |
Output is correct |
18 |
Correct |
976 ms |
33568 KB |
Output is correct |
19 |
Correct |
962 ms |
34240 KB |
Output is correct |
20 |
Execution timed out |
4081 ms |
33800 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |