#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[500000], dp[500000];
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)));
while (q.size() > 1 && calc(q.back(), i) - calc(q[q.size() - 2], i) <=
calc(i, i) - calc(q.back(), i))
q.pop_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 |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
2168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
2296 KB |
Output is correct |
2 |
Correct |
15 ms |
2248 KB |
Output is correct |
3 |
Incorrect |
20 ms |
2300 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
31 ms |
3324 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
69 ms |
7272 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
12720 KB |
Output is correct |
2 |
Correct |
100 ms |
10616 KB |
Output is correct |
3 |
Incorrect |
105 ms |
11388 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
159 ms |
17908 KB |
Output is correct |
2 |
Correct |
156 ms |
15092 KB |
Output is correct |
3 |
Incorrect |
138 ms |
16120 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
155 ms |
15504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |