代码

#pragma GCC optimize("O3")
#pragma GCC optimize("O2")
#pragma GCC optimize("Og")
#pragma GCC optimize("inline")
#pragma GCC optimize("Ofast")
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define ed end
#define bg begin
#define fr first
#define sc second
#define il inline
#define LL long long
#define pb push_back
#define mk make_pair
#define to(k) E[k].to
#define val(k) E[k].val
#define next(k) E[k].next
#define pint pair<int, int>

#define rg register
#define MAXN 1000009

double kk[MAXN] ;
using namespace std ;
int N, base[MAXN], dp[2][MAXN] ;

const int ch_top=6e7+3;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;

inline int read(){
    while(*++now_r<'0');
    register int x=*now_r-'0';
    while(*++now_r>='0')x=x*10+*now_r-'0';
    return x;
}
inline void write(int x){
    static char st[20];static int top;
    while(st[++top]='0'+x%10,x/=10);
    while(*++now_w=st[top],--top);
    *++now_w='\n';
}
bool check(int val, int p){
	rg double ret = 0 ; 
	for (rg int i = 1 ; i <= N ; ++ i)
		ret = max(ret, base[i] - val + sqrt(abs(p - i))) ;
	return (bool)(ret <= base[p]) ;
}
void solve(int l, int r, int ul, int ur, int *f){
	if (l > r) return ;
	double ans = 0, t_now ;  
	int mid = (l + r) >> 1, umid = ul, o = min(mid, ur) ;
	for (int j = ul ; j <= o ; ++ j){
		t_now = base[j] + kk[mid - j] - base[mid] ; 
		if (t_now > ans) ans = t_now, umid = j ; 
	}
	f[mid] = ceil(ans), solve(l, mid - 1, ul, umid, f), solve(mid + 1, r, umid, ur, f) ; 
}
il int qr(){
	char c = getchar() ; int res = 0 ; 
	while (!isdigit(c)) c = getchar() ; 
	while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar() ;
	return res ;
}
int main(){
    fread(ch, 1, ch_top, stdin) ; N = read() ; int i ;
	for (i = 1 ; i <= N ; ++ i) base[i] = read(), kk[i] = sqrt(i) ; 
 	if (N <= 500){
		for (i = 1 ; i <= N ; ++ i){
			int l = 1, r = 2e9, mid, ans = 0 ; 
			while (l <= r){
				mid = (l + r) >> 1 ; 
				if (check(mid, i)) ans = mid, r = mid - 1 ;
				else l = mid + 1 ; 
			}
			write(ans) ;  
		}
		fwrite(ch,1,now_w-ch,stdout) ; return 0 ; 
	}
	solve(1, N, 1, N, dp[0]), 
	reverse(base + 1, base + N + 1), 
	solve(1, N, 1, N, dp[1]) ;
	for (i = 1 ; i <= N ; ++ i) 
		write(max(dp[0][i], dp[1][N - i + 1])) ;
	fwrite(ch,1,now_w-ch,stdout) ; return 0 ; 
}

评测结果