#include<bits/stdc++.h>
using namespace std;
#define int int64_t
const int N = 500005;
int h[N],ans[N];
int ftable[N];
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;
while(now.l <= v.back().l && h[v.back().i] + f(v.back().i,v.back().l) < h[i] + f(i,v.back().l)){
v.pop_back();
}
if(h[v.back().i] + f(v.back().i,v.back().r) >= h[i] + f(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] + f(pre.i,m) >= h[i] + f(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;
//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] << ' '; 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:32:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l+r >> 1;
~^~
pio.cpp: In function 'int32_t main()':
pio.cpp:59:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i=1;i<=n;i++) cout << ans[i] - h[i] << ' '; cout << '\n';
^~~
pio.cpp:59:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(int i=1;i<=n;i++) cout << ans[i] - h[i] << ' '; cout << '\n';
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
4224 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4224 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4224 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1083 ms |
5376 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1087 ms |
5892 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
6052 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1095 ms |
6488 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
8952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
13432 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
17144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1092 ms |
14584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
