#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (ll i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;
ll h[300000], dp[300000];
double calc(ll k, ll i) {
return h[k] + sqrt(abs(i - k));
}
int main() {
iostream::sync_with_stdio(false);
cin.tie(0);
ll n;
cin >> n;
FOR(i, 0, n) {
cin >> h[i];
dp[i] = h[i];
}
deque<ll> 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], (ll)ceil(calc(q[0], i)));
if (h[i] > h[q.back()]) q.push_back(i);
}
q.clear();
q.push_back(n - 1);
for (ll 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], (ll)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 |
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 |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 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 |
1664 KB |
Output is correct |
2 |
Correct |
13 ms |
1656 KB |
Output is correct |
3 |
Incorrect |
17 ms |
1912 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
2396 KB |
Output is correct |
2 |
Correct |
26 ms |
2296 KB |
Output is correct |
3 |
Incorrect |
26 ms |
2808 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
60 ms |
4984 KB |
Output is correct |
2 |
Correct |
56 ms |
4848 KB |
Output is correct |
3 |
Incorrect |
55 ms |
5596 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
54 ms |
9976 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 |
55 ms |
9980 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 |
54 ms |
9948 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |