#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9+10;
struct func {
int h, i; long double l, r;
};
int n;
int mx1[500000];
int mx2[500000];
int H[500000];
int Sqrt[500000];
int eval(func f, int i) {
return f.h+Sqrt[abs(i-f.i)];
assert(i>=f.i);
return f.h+Sqrt[i-f.i];
}
// returns when right part of func a intersects func b
long double intersectRight(func a, func b) {
if (a.h>=b.h) return inf;
long long d = b.h-a.h;
if (b.i-a.i-d*d<0) return -1;
long double x = (b.i-a.i)/2.0/d-d/2.0;
long double ans = x*x+b.i;
//assert(ans < n && ans >= 0);
//assert(eval(a, ans) == eval(b, ans));
return ans;
}
void solveRight(int mx[]) {
vector<func> s;
for (int i = 0; i < n; i++) {
func f = {H[i], i, 0, n-1};
while (!s.empty()) {
func f2 = s.back();
long double intersect = intersectRight(f2, f);
//cout << f2.i << " intersects " << f.i << " at " << intersect << endl;
if (intersect <= f2.l) {
s.pop_back();
/*
s.top().r = f.l-1;
break;
*/
} else {
if (intersect - 1 <= n-1) s.back().r = intersect - 1;
f.l = intersect;
break;
}
}
if (f.l <= n-1) s.push_back(f);
//assert(f.l >= i);
}
//for (func f : s) cout << f.i << " " << f.l << " " << f.r << "\n";
while (!s.empty()) {
func f = s.back(); s.pop_back();
assert(f.l >= 0 && f.r <= n-1);
//cout << f.i << " is max from " << f.l << " to " << f.r << endl;
for (int i = ceil(f.l); i <= floor(f.r); i++) {
//cout << i << " = " << f.i << " (" << eval(f, i) << ")" << "\n";
mx[i] = max(mx[i], eval(f, i));
/*
for (int j = 0; j <= i; j++) {
if (eval({H[j],j,0,n-1}, i) > mx[i]) {
cout << "Eval: " << eval({H[j],j,0,n-1}, i) << " better than " << mx[i] << endl;
cout << j << " " << i << endl;
}
}
*/
}
}
for (int i = 0; i < n; i++) {
//cout << "mx[" << i << "] = " << mx[i] << endl;
}
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
Sqrt[0] = 0;
for (int i = 1; i <= 1000; i++) {
for (int j = (i-1)*(i-1)+1; j <= min(i*i, n-1); j++) Sqrt[j] = i;
}
for (int i = 0; i < n; i++) {
cin >> H[i]; mx1[i] = mx2[i] = 0;
}
solveRight(mx1);
for (int i = 0; i < n/2; i++) {
swap(H[i], H[n-i-1]);
}
solveRight(mx2);
for (int i = 0; i < n/2; i++) {
swap(H[i], H[n-i-1]);
}
for (int i = 0; i < n; i++) {
mx1[i] = max(mx1[i], mx2[n-1-i]);
}
for (int i = 0; i < n; i++) {
cout << mx1[i]-H[i] << "\n";
}
return 0;
}
Compilation message
pio.cpp: In function 'void solveRight(int*)':
pio.cpp:38:32: warning: narrowing conversion of '(n - 1)' from 'int' to 'long double' inside { } [-Wnarrowing]
func f = {H[i], i, 0, n-1};
~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
2176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
2352 KB |
Output is correct |
| 2 |
Correct |
10 ms |
1792 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
2304 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
3368 KB |
Output is correct |
| 2 |
Correct |
26 ms |
3320 KB |
Output is correct |
| 3 |
Incorrect |
23 ms |
3448 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
7288 KB |
Output is correct |
| 2 |
Correct |
53 ms |
6908 KB |
Output is correct |
| 3 |
Incorrect |
52 ms |
6904 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
11932 KB |
Output is correct |
| 2 |
Correct |
96 ms |
9976 KB |
Output is correct |
| 3 |
Incorrect |
81 ms |
11384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
16744 KB |
Output is correct |
| 2 |
Correct |
126 ms |
13560 KB |
Output is correct |
| 3 |
Incorrect |
114 ms |
15772 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
14328 KB |
Output is correct |
| 2 |
Correct |
123 ms |
14200 KB |
Output is correct |
| 3 |
Incorrect |
113 ms |
15608 KB |
Output isn't correct |
