| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 29587 |
2017-07-20T07:35:59 Z |
시제연(#1241) |
Lightning Conductor (POI11_pio) |
C++11 |
|
1000 ms |
17648 KB |
#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, j;
for (i=n-1;i>=0;i--) {
ll maxi = 0, s = 0, e = 1234567;
while(s<=e) {
ll m = (s+e)>>1;
int flag = 1;
for (j=n-1;j>i;j--) {
if (j!=n-1&&h[j]<=h[j+1]) continue;
if (!(h[j]-h[i]<=m&&(j-i)<=(h[i]-h[j]+m)*(h[i]-h[j]+m))) flag = 0;
if (!flag) break;
}
if (flag) e = m-1;
else s = m+1;
}
ans[i] = s;
}
}
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:68:6: warning: unused variable 'maxi' [-Wunused-variable]
ll maxi = 0, s = 0, e = 1234567;
^
pio.cpp: In function 'int main()':
pio.cpp:87:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
pio.cpp:90:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&x);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
17648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
17648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
123 ms |
17648 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
309 ms |
17648 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
17648 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
17648 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
17648 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
17648 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
17648 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1000 ms |
17648 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
