#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n, a[N];
double f[N], ans[N];
void cdq(int l, int r, int L, int R) {
int MID = (L+R)>>1, mid, loc = MID;
if (r < loc) loc = r;
mid = loc; f[MID] = sqrt(1.*MID-loc)+a[loc]-a[MID];
for (int i = l; i < loc; i++)
if (a[i]-a[MID]+sqrt(1.*MID-i) >= f[MID])
mid = i, f[MID] = sqrt(1.*MID-i)+a[i]-a[MID];
if (L < MID) cdq(l, mid, L, MID-1);
if (MID < R) cdq(mid, r, MID+1, R);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
cdq(1, n, 1, n);
swap(ans, f);
reverse(a+1, a+n+1);
cdq(1, n, 1, n);
for (int i = 1; i <= n; i++)
printf("%d\n", int(ceil(max(ans[i], f[n-i+1]))));
return 0;
}
Compilation message
pio.cpp: In function 'int main()':
pio.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
19 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
pio.cpp:20:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
20 | for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8172 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
8172 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
8172 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
8812 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
9344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
9324 KB |
Output is correct |
2 |
Correct |
30 ms |
8812 KB |
Output is correct |
3 |
Correct |
32 ms |
9324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
10012 KB |
Output is correct |
2 |
Correct |
47 ms |
9964 KB |
Output is correct |
3 |
Correct |
57 ms |
10112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
12524 KB |
Output is correct |
2 |
Correct |
103 ms |
12012 KB |
Output is correct |
3 |
Correct |
98 ms |
12012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
158 ms |
16364 KB |
Output is correct |
2 |
Correct |
154 ms |
14444 KB |
Output is correct |
3 |
Correct |
151 ms |
15084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
234 ms |
20060 KB |
Output is correct |
2 |
Correct |
220 ms |
17004 KB |
Output is correct |
3 |
Correct |
210 ms |
18028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
231 ms |
17516 KB |
Output is correct |
2 |
Correct |
246 ms |
17004 KB |
Output is correct |
3 |
Correct |
210 ms |
18028 KB |
Output is correct |