#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 = 2;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]<<"\n";
}
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
5680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
165 ms |
9420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
294 ms |
11900 KB |
Output is correct |
2 |
Correct |
268 ms |
11840 KB |
Output is correct |
3 |
Correct |
262 ms |
12256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
621 ms |
17548 KB |
Output is correct |
2 |
Correct |
588 ms |
18572 KB |
Output is correct |
3 |
Correct |
780 ms |
18648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1056 ms |
40172 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1071 ms |
61284 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
171 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
170 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |