#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 5e5 + 10;
int n, h[N];
struct Line {
int a, b, x;
int operator()(int x) {
return ceil(sqrt(abs(a - x))) + b;
}
int operator[](int x) {
return sqrt(abs(a - x)) + b;
}
int operator < (const Line& other) const {
if (x != other.x) return x < other.x;
if (a != other.a) return a < other.a;
return b < other.b;
}
};
int intersect(Line L1, Line L2) {
int L = max(L1.a, L2.a), R = n + 1;
while (R - L > 1) {
int mid = L + R >> 1;
if (L1[mid] >= L2[mid]) L = mid;
else R = mid;
}
if (L1[L] < L2[L]) return L;
else return R;
}
int bad(Line L1, Line L2, Line L3) {
return intersect(L1, L3) <= intersect(L1, L2);
}
int f[N];
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> h[i];
vector <Line> convex;
for (int i = 1, cur = 0; i <= n; ++i) {
if (i > 1) {
auto iter = --lower_bound(convex.begin(), convex.end(), (Line){1e9, 1e9, i});
f[i] = max(f[i], - h[i] + (*iter)(i));
}
//
if (convex.size() && h[i] <= cur) continue;
Line L = {i, h[i], 0};
cur = h[i];
while (convex.size() >= 2 && bad(convex.end()[-2], convex.back(), L)) convex.pop_back();
L.x = (convex.empty() ? 1 : intersect(convex.back(), L));
convex.push_back(L);
}
convex.clear();
reverse(h + 1, h + n + 1);
for (int i = 1, cur = 0; i <= n; ++i) {
if (i > 1) {
auto iter = --lower_bound(convex.begin(), convex.end(), (Line){1e9, 1e9, i});
f[n - i + 1] = max(f[n - i + 1], - h[i] + (*iter)(i));
}
//
if (convex.size() && h[i] <= cur) continue;
Line L = {i, h[i], 0};
cur = h[i];
while (convex.size() >= 2 && bad(convex.end()[-2], convex.back(), L)) convex.pop_back();
L.x = (convex.empty() ? 1 : intersect(convex.back(), L));
convex.push_back(L);
}
for (int i = 1; i <= n; ++i) cout << f[i] << '\n';
}
Compilation message
pio.cpp: In function 'int intersect(Line, Line)':
pio.cpp:35:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid = L + R >> 1;
| ~~^~~
pio.cpp: In function 'int main()':
pio.cpp:56:87: error: narrowing conversion of '1.0e+9' from 'double' to 'int' [-Wnarrowing]
56 | auto iter = --lower_bound(convex.begin(), convex.end(), (Line){1e9, 1e9, i});
| ^
pio.cpp:71:87: error: narrowing conversion of '1.0e+9' from 'double' to 'int' [-Wnarrowing]
71 | auto iter = --lower_bound(convex.begin(), convex.end(), (Line){1e9, 1e9, i});
| ^
