#include<bits/stdc++.h>
using namespace std;
#define int int64_t
const int N = 500005;
int h[N],ans[N];
int ftable[N],ftable2[N];
double f2(int i,int j){
return ftable2[abs(i-j)];
}
int f(int i,int j){
return ftable[abs(i-j)];
}
struct segment{
int i,l,r;
};
void solve(int n){
vector<segment> v;
v.push_back({1,1,n});
for(int i=2;i<=n;i++){
segment now; now.i = i; now.l = i; now.r = n;
//cout << i << " : "; for(auto i : v) cout << i.i << ' ' << complex<int>(i.l,i.r) << ' '; cout << '\n';
while(now.l <= v.back().l && h[v.back().i] + f2(v.back().i,v.back().l) <= h[i] + f2(i,v.back().l)
&& h[v.back().i] + f2(v.back().i,v.back().r) <= h[i] + f2(i,v.back().r)){
v.pop_back();
}
//cout << i << " : "; for(auto i : v) cout << i.i << ' ' << complex<int>(i.l,i.r) << ' '; cout << '\n';
//cout << i << " : " << h[v.back().i] + f2(v.back().i,v.back().r) << ' ' << h[i] + f2(i,v.back().r) << '\n';
if(h[v.back().i] + f2(v.back().i,v.back().r) >= h[i] + f2(i,v.back().r)) {
if(v.back().r != n) v.push_back({now.i,v.back().r+1,now.r});
continue;
}
auto pre = v.back();
int l = max(v.back().l,now.l), r = v.back().r;
//cout << i << " : " << l << ' ' << r << '\n';
while(l < r){
int m = l+r >> 1;
if(h[pre.i] + f2(pre.i,m) > h[i] + f2(i,m)) l=m+1;
else r = m;
}
now.l = l;
v[v.size()-1].r = l-1;
v.push_back(now);
}
for(auto i : v) for(int j=i.l;j<=i.r;j++) ans[j] = max(ans[j],h[i.i] + f(i.i,j));
}
int32_t main(){
cin.tie(0); ios_base::sync_with_stdio(false);
for(int i=1,now=1;i<N;i++){
if(now*now<i) now++;
ftable[i] = now;
ftable2[i] = sqrt(i);
//if(i<10)cout << i << ' ' << ftable[i] << '\n';
}
int n;
cin >> n;
for(int i=1;i<=n;i++) cin >> h[i];
solve(n);
reverse(h+1,h+n+1);
reverse(ans+1,ans+n+1);
solve(n);
reverse(ans+1,ans+n+1);
reverse(h+1,h+n+1);
for(int i=1;i<=n;i++) cout << ans[i] - h[i] << '\n'; //cout << '\n';
// for(int i=1;i<=n;i++){
// int mx = 0;
// for(int j=1;j<=n;j++) mx = max(mx,h[j]+f(i,j));
// cout << mx-h[i] << ' ';
// }cout << '\n';
}
Compilation message
pio.cpp: In function 'void solve(int64_t)':
pio.cpp:40:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l+r >> 1;
~^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
8192 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
8192 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
8192 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
8952 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
20 ms |
9472 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
24 ms |
9464 KB |
Output is correct |
| 2 |
Correct |
19 ms |
9472 KB |
Output is correct |
| 3 |
Incorrect |
23 ms |
9740 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
30 ms |
10180 KB |
Output is correct |
| 2 |
Correct |
40 ms |
10104 KB |
Output is correct |
| 3 |
Incorrect |
29 ms |
10744 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
61 ms |
12920 KB |
Output is correct |
| 2 |
Correct |
67 ms |
12664 KB |
Output is correct |
| 3 |
Incorrect |
56 ms |
13304 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
92 ms |
17140 KB |
Output is correct |
| 2 |
Correct |
88 ms |
15096 KB |
Output is correct |
| 3 |
Incorrect |
85 ms |
17272 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
132 ms |
20984 KB |
Output is correct |
| 2 |
Correct |
119 ms |
18040 KB |
Output is correct |
| 3 |
Incorrect |
112 ms |
21008 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
126 ms |
18552 KB |
Output is correct |
| 2 |
Correct |
124 ms |
18000 KB |
Output is correct |
| 3 |
Incorrect |
120 ms |
20984 KB |
Output isn't correct |
