#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef __int128 ll;
typedef pair<ll,ll> pll;
ll ccw(const pll &a, const pll &b, const pll &c) {return a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;}
bool cmp(const pll &A, const pll &B) {return A.x*B.y<B.x*A.y;}
ll INF = 1LL<<40;
struct CHT {
vector<pll> vec;
void init() {
vec.clear();
}
void add(ll x, ll y) {
pll t = pll(x,y);
//while(vec.size()>=2&&ccw(vec[vec.size()-2],vec.back(),t)>=0) vec.pop_back();
vec.push_back(t);
}
pll g(pll a, pll b) {return pll(a.second-b.second,b.first-a.first);}
pll f(pll a, pll x) {return pll(x.y*(a.x*x.x+a.y*x.y)-x.x*x.x,x.y*x.y);}
ll bs(pll a, ll y) {
ll s = vec.back().x/2, e = 1234567;
while(s<=e) {
ll m =(s+e)>>1;
if (a.x*m+a.y-m*m<=y) e = m-1;
else s = m+1;
}
return s;
}
ll getv(ll y) {
if (vec.empty()) return -INF;
ll s = vec.back().x/2, e = 1234567;
while(s<=e) {
ll m = (s+e)>>1;
bool flag = 1;
for (int i=0;i<vec.size();i++) {
if (vec[i].x*m+vec[i].y-m*m>y) flag = 0;
}
if (flag) e = m-1;
else s = m+1;
}
return s;
/*
int s = 0, e = (int)vec.size()-2;
while(s<=e) {
int m = (s+e)>>1;
if (cmp(f(vec[m],g(vec[m],vec[m+1])),pll(y,1))) e = m-1;
else s = m+1;
}
return bs(vec[s],y);
*/
}
} cht;
int n;
ll arr[500100];
long long ans[2][500100];
void solve(ll h[],long long ans[]) {
int i; ll maxi = -1;
cht.init();
for (i=n-1;i>=0;i--) {
long long v = cht.getv(i);
ans[i] = max(v-(long long)h[i],0LL);
//if (maxi<h[i])
cht.add(2*h[i],1LL*i-h[i]*h[i]);
//maxi = max(maxi,h[i]);
}
}
int main() {
int i;
scanf("%d",&n);
for (i=0;i<n;i++) {
long long x;
scanf("%lld",&x);
arr[i] = x;
}
solve(arr,ans[0]);
reverse(arr,arr+n);
solve(arr,ans[1]);
reverse(ans[1],ans[1]+n);
for (i=0;i<n;i++) {
printf("%lld\n",(long long)max(ans[0][i],ans[1][i]));
}
return 0;
}
Compilation message
pio.cpp: In member function 'll CHT::getv(ll)':
pio.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<vec.size();i++) {
^
pio.cpp: In function 'void solve(ll*, long long int*)':
pio.cpp:66:12: warning: unused variable 'maxi' [-Wunused-variable]
int i; ll maxi = -1;
^
pio.cpp: In function 'int main()':
pio.cpp:80:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
pio.cpp:83:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&x);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
17648 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
17648 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
53 ms |
17788 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
99 ms |
19268 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
243 ms |
20804 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
339 ms |
20804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
203 ms |
23876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1000 ms |
30020 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1000 ms |
30020 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1000 ms |
30020 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1000 ms |
42308 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
