#include <bits/stdc++.h>
using namespace std ;
#define int long long
int logg[500001];
int table[500001][20];
int qu(int l,int r){
int ge = logg[r-l+1];
return max(table[l][ge],table[r-(1<<ge)+1][ge]);
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;cin>>n;
int arr[n];
for(int i = 0;i<n;i++){
cin>>arr[i];
table[i][0] = arr[i];
}
logg[1] = 0;
for(int i = 1;i<=n;i++)logg[i] = logg[i/2]+1;
for(int j = 1;j<20;j++){
for(int i = 0;i<n;i++){
if(i+(1<<j)<=n){
table[i][j] = max(table[i][j-1],table[i+(1<<(j-1))][j-1]);
}
}
}
for(int i = 0;i<n;i++){
int st = i+1,len = 1;
int all =arr[i] ;
while(st<n){
int en = min(n-1,i+(len*len));
all = max(all,qu(st,en)+len);
st = en+1;len++;
}
st = i-1;len = 1;
while(st>=0){
int en = max(0LL,i-(len*len));
all = max(all,qu(en,st)+len);
st = en-1;len++;
}
cout<<all-arr[i]<<endl;
}
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
93 ms |
5844 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
237 ms |
9336 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
376 ms |
11708 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
713 ms |
17816 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1072 ms |
39960 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1072 ms |
61376 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
87 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
65 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |