Submission #29572

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
29572	2017-07-20T06:59:30 Z	시제연(#1241)	Lightning Conductor (POI11_pio)	C++11	9 / 100	219 ms	17652 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 operator < (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);}
	pll fi(pll a, ll y) {return pll(y-a.y,a.x);}
	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;
        int s = 0, e = (int)vec.size()-2;
        while(s<=e) {
			int m = (s+e)>>1;
			if (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 function 'int main()':
pio.cpp:67:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
pio.cpp:70:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&x);
                   ^

Subtask #1
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	17652 KB	Output isn't correct

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	17652 KB	Output isn't correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	17652 KB	Output is correct

Subtask #4
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	13 ms	17652 KB	Output isn't correct

Subtask #5
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	17652 KB	Output isn't correct

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	36 ms	17652 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	36 ms	17652 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	109 ms	17652 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	149 ms	17652 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	216 ms	17652 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	219 ms	17652 KB	Output isn't correct
2	Halted	0 ms	0 KB	-