#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int nax = 500'005;
void self_max(int& me, int other) {
me = max(me, other);
}
int lg[nax];
int mx[nax][19];
int q(int l, int r) {
int L = lg[r-l+1];
return max(mx[l][L], mx[r-(1<<L)+1][L]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for(int& i : a) {
cin >> i;
}
vector<int> ans(n, 0);
lg[1] = 0;
for(int i = 2; i < n; i++) {
lg[i] = lg[i/2] + 1;
}
for(int i = 0; i < n; i++) {
mx[i][0] = a[i];
}
for(int j = 1; j < 19; j++) {
for(int i = 0; i < n; i++) {
mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
}
}
//for(int i = 0; i < n; i++) {
//for(int j = i; j < n; j++) {
//cout << i << " " << j << ": " << q(i, j) << "\n";
//}
//}
for(int i = 0; i < n; i++) {
bool in = true;
for(int p = 1; in; p++) {
in = false;
int sz = p*p;
int prev = (p-1)*(p-1);
// left interval
int l = max(0, i-sz);
int r = i - prev - 1;
if (l <= r) {
self_max(ans[i], p - a[i] + q(l, r));
in = true;
}
// right inteval
l = i + prev + 1;
r = min(n-1, i + sz);
//if (i == 0) {
//cout << l << " " << r << "\n";
//}
if (l <= r && r < n) {
self_max(ans[i], p - a[i] + q(l, r));
in = true;
}
}
}
for(int i = 0; i < n; i++) {
cout << ans[i] << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
3296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
155 ms |
5264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
230 ms |
6324 KB |
Output is correct |
2 |
Correct |
195 ms |
6328 KB |
Output is correct |
3 |
Correct |
200 ms |
6828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
554 ms |
9300 KB |
Output is correct |
2 |
Correct |
495 ms |
10152 KB |
Output is correct |
3 |
Correct |
548 ms |
10256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1081 ms |
20128 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1094 ms |
30680 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
175 ms |
65536 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
185 ms |
65536 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |