oj.uz

Submission #29529

# Submission time Handle Problem Language Result Execution time Memory
29529 2017-07-20T05:21:43 Z 시제연(#1241) Lightning Conductor (POI11_pio) C++11
0 / 100
 173 ms 13740 KB 
#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long 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);}
	ll f(pll a, ll x) {return a.x*x+a.y;}
	pll fi(pll a, ll y) {return pll(y-a.y,a.x);}
	ll bs(pll a, ll y) {
		ll s = a.x/2, e = 1234567;
		while(s<=e) {
			ll m =(s+e)>>1;
			if (f(a,m)-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 (g(vec[m],vec[m+1])<fi(vec[m+1],y)) s = m+1;
			else e = m-1;
        }
		return bs(vec[s],y);
	}
} cht;

int n;
ll arr[500100];
ll ans[2][500100];

void solve(ll h[],ll ans[]) {
	int i; ll maxi = -1;
	cht.init();
	for (i=n-1;i>=0;i--) {
		ll v = cht.getv(i);
		ans[i] = max(v-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++) scanf("%lld",&arr[i]);
	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",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:68:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i=0;i<n;i++) scanf("%lld",&arr[i]);
                                         ^

Subtask #1
0 / 9.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 10.0

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