oj.uz

답안 #29587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29587 2017-07-20T07:35:59 Z 시제연(#1241) Lightning Conductor (POI11_pio) C++11
27 / 100
 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);
                   ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 17648 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 17648 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 17648 KB Output is correct

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 123 ms 17648 KB Output isn't correct

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 309 ms 17648 KB Output isn't correct

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 17648 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 17648 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 17648 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 17648 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 17648 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 17648 KB Execution timed out
2 Halted 0 ms 0 KB -