#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> p2;
const int N=5e5+5;
const int inf=1e9;
int n;
int h[N],dp[N];
void solvel(int l,int r,int optl,int optr){
if(l>r)return;
int mid=(l+r)/2;
p2 res(-inf,-1);
for(int i=optl;i<=min(mid,optr);i++)res=max(res,p2(h[i]+ceil(sqrt(mid-i))-h[mid],i));
dp[mid]=max(dp[mid],res.first);
int opt=res.second;
solvel(l,mid-1,optl,opt);
solvel(mid+1,r,opt,optr);
}
void solver(int l,int r,int optl,int optr){
if(l>r)return;
int mid=(l+r)/2;
p2 res(-inf,-1);
for(int i=max(mid,optl);i<=optr;i++)res=max(res,p2(h[i]+ceil(sqrt(i-mid))-h[mid],i));
dp[mid]=max(dp[mid],res.first);
int opt=res.second;
solver(l,mid-1,optl,opt);
solver(mid+1,r,opt,optr);
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
for(int i=1;i<=n;i++)cin >> h[i];
solvel(1,n,1,n);
solver(1,n,1,n);
for(int i=1;i<=n;i++)cout << dp[i] << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
3052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
2908 KB |
Output is correct |
2 |
Incorrect |
17 ms |
2908 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
3180 KB |
Output is correct |
2 |
Incorrect |
37 ms |
3152 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
4180 KB |
Output is correct |
2 |
Incorrect |
88 ms |
4364 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
111 ms |
7096 KB |
Output is correct |
2 |
Incorrect |
147 ms |
5052 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
9144 KB |
Output is correct |
2 |
Incorrect |
211 ms |
6396 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
158 ms |
6736 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |