#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;
int h[300000], dp[300000];
double calc(int k, int i) {
return h[k] + sqrt(abs(i - k));
}
int main() {
iostream::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
FOR(i, 0, n) {
cin >> h[i];
dp[i] = h[i];
}
deque<int> q;
q.push_back(0);
FOR(i, 1, n) {
while (q.size() > 1 && calc(q[0], i) <= calc(q[1], i)) q.pop_front();
dp[i] = max(dp[i], (int)ceil(calc(q[0], i)));
if (h[i] > h[q.back()]) q.push_back(i);
}
q.clear();
q.push_back(n - 1);
for (int i = n - 1; i >= 0; i--) {
while (q.size() > 1 && calc(q[0], i) <= calc(q[1], i)) q.pop_front();
dp[i] = max(dp[i], (int)ceil(calc(q[0], i)));
if (h[i] > h[q.back()]) q.push_back(i);
}
FOR(i, 0, n) cout << dp[i] - h[i] << '\n';
return 0;
}
Compilation message
pio.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
#pragma GCC Optimize("O3")
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
1656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
1784 KB |
Output is correct |
2 |
Correct |
13 ms |
1244 KB |
Output is correct |
3 |
Incorrect |
17 ms |
1788 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
2524 KB |
Output is correct |
2 |
Correct |
26 ms |
2552 KB |
Output is correct |
3 |
Incorrect |
28 ms |
2680 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
5496 KB |
Output is correct |
2 |
Correct |
56 ms |
5208 KB |
Output is correct |
3 |
Incorrect |
61 ms |
5076 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
51 ms |
8348 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
53 ms |
8196 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
51 ms |
8348 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |