#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9+10;
struct func {
int h, i, l, r;
};
int n;
int mx[500000];
int mx2[500000];
int H[500000];
int Sqrt[500000];
int eval(func f, int i) {
return f.h+Sqrt[i-f.i];
}
// returns when right part of func a intersects func b
int intersectRight(func a, func b) {
if (eval(a, n) >= eval(b, n)) 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 long ans = ceil(x*x)+b.i;
assert(ans < n);
return ans;
}
void solveRight(int mx[]) {
stack<func> s;
for (int i = 0; i < n; i++) {
func f = {H[i], i, i, n-1};
while (!s.empty()) {
func f2 = s.top();
int intersect = intersectRight(f2, f);
//cout << f2.i << " intersects " << f.i << " at " << intersect << endl;
if (intersect <= f2.l) s.pop();
else {
if (intersect - 1 <= n-1) s.top().r = intersect - 1;
f.l = intersect;
break;
}
}
if (f.l <= n-1) s.push(f);
assert(f.l >= i);
}
while (!s.empty()) {
func f = s.top(); s.pop();
//cout << f.i << " is max from " << f.l << " to " << f.r << endl;
for (int i = f.l; i <= f.r; i++) mx[i] = max(mx[i], eval(f, i));
}
for (int i = 0; i < n; i++) {
//cout << "mx[" << i << "] = " << mx[i] << endl;
}
}
int main() {
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]; mx[i] = H[i];
}
solveRight(mx);
for (int i = 0; i < n/2; i++) {
swap(H[i], H[n-i-1]);
}
solveRight(mx2);
for (int i = 0; i < n; i++) {
mx[i] = max(mx[i], mx2[n-1-i]);
}
for (int i = 0; i < n/2; i++) {
swap(H[i], H[n-i-1]);
}
for (int i = 0; i < n; i++) {
cout << mx[i]-H[i] << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
1408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
38 ms |
1912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
2296 KB |
Output is correct |
2 |
Incorrect |
27 ms |
1784 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
71 ms |
3296 KB |
Output is correct |
2 |
Correct |
69 ms |
3192 KB |
Output is correct |
3 |
Incorrect |
52 ms |
3576 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
163 ms |
7032 KB |
Output is correct |
2 |
Correct |
148 ms |
6812 KB |
Output is correct |
3 |
Incorrect |
123 ms |
6776 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
250 ms |
11384 KB |
Output is correct |
2 |
Correct |
252 ms |
9336 KB |
Output is correct |
3 |
Incorrect |
198 ms |
11360 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
351 ms |
15224 KB |
Output is correct |
2 |
Incorrect |
349 ms |
12024 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
357 ms |
12556 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |