#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
const int MAXN = 500005;
double sqr[MAXN], ans[MAXN];
int n, a[MAXN];
void solve(int s, int e, int ps, int pe, int rev){
if(s > e) return;
int m = (s+e)/2;
int opt = -1;
double mx = -1e9;
for(int i=ps; i<=pe && i<m; i++){
double cur = a[i] + sqr[m - i];
if(cur > mx){
mx = cur;
opt = i;
}
}
if(rev) ans[n+1-m] = max(ans[n+1-m], mx);
else ans[m] = max(ans[m], mx);
solve(s, m-1, ps, opt, rev);
solve(m+1, e, opt, pe, rev);
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
sqr[i] = sqrt(i);
}
solve(1, n, 1, n, 0);
reverse(a+1, a+n+1);
solve(1, n, 1, n, 1);
reverse(a+1, a+n+1);
for(int i=1; i<=n; i++){
int cu = (int)ceil(ans[i]);
printf("%d\n", max(cu - a[i], 0));
}
}
Compilation message
pio.cpp: In function 'int main()':
pio.cpp:30:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
pio.cpp:32:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
11796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
11796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
11796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
11796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
11796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
11796 KB |
Output is correct |
2 |
Correct |
16 ms |
11796 KB |
Output is correct |
3 |
Correct |
16 ms |
11796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
11796 KB |
Output is correct |
2 |
Correct |
33 ms |
11796 KB |
Output is correct |
3 |
Correct |
49 ms |
11796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
11796 KB |
Output is correct |
2 |
Correct |
86 ms |
11796 KB |
Output is correct |
3 |
Correct |
89 ms |
11796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
166 ms |
11796 KB |
Output is correct |
2 |
Correct |
153 ms |
11796 KB |
Output is correct |
3 |
Correct |
116 ms |
11796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
229 ms |
11796 KB |
Output is correct |
2 |
Correct |
199 ms |
11796 KB |
Output is correct |
3 |
Correct |
166 ms |
11796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
226 ms |
11796 KB |
Output is correct |
2 |
Correct |
183 ms |
11796 KB |
Output is correct |
3 |
Correct |
209 ms |
11796 KB |
Output is correct |