Submission #29589

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
29589	2017-07-20T07:41:15 Z	김현수(#1240)	Lightning Conductor (POI11_pio)	C++14	100 / 100	343 ms	13752 KB

pio

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 500005;
const double eps = 1e-9;

ll n, a[N], ans[N];
double rt[N];

double val (pll &P, ll I) {return P.Y + rt[I - P.X];}

ll its (pll &A, pll &B) {
	ll S = A.X, E = n+1;
	while(S<E) {
		ll M = (S+E)/2;
		val(A, M) - val(B, M) + eps > 0 ? E = M : S = M+1;
	}
	return S;
}

struct hull {
	vector<pll> v;
	void clear () {v.clear();}
	void upd (pll A) {
		if(v.empty()) {v.push_back(A); return;}
		if(its(A, v.back()) == n+1) return;
		for(ll i=v.size();i-->1;) {
			if(its(v[i], v[i-1]) < its(A, v[i])) break;
			else v.pop_back();
		}
		v.push_back(A);
	}
	double get (ll P) {
		if(v.empty()) return 0;
		ll S = 0, E = (int)v.size()-1;
		while(S<E) {
			ll M = (S+E)/2;
			val(v[M], P) < val(v[M+1], P) ? S = M+1 : E = M;
		}
		return val(v[S], P);
	}
} h;

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(ll i=1;i<=n;i++) rt[i] = sqrt(i);
	for(ll i=1;i<=n;i++) {
		ans[i] = max(ans[i], (ll)(ceil(h.get(i) - a[i]) + eps));
		h.upd(pll(i, a[i]));
	}
	h.clear();
	for(ll i=n;i>=1;i--) {
		ans[i] = max(ans[i], (ll)(ceil(h.get(n-i+1) - a[i]) + eps));
		h.upd(pll(n-i+1, a[i]));
	}
	for(ll i=1;i<=n;i++) printf("%lld\n",ans[i]);
}

Compilation message

pio.cpp: In function 'int main()':
pio.cpp:49:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
pio.cpp:50:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
                                          ^

Subtask #1

9.0 / 9.0

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

Subtask #2

9.0 / 9.0

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

Subtask #3

9.0 / 9.0

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

Subtask #4

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	13752 KB	Output is correct

Subtask #5

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	13752 KB	Output is correct

Subtask #6

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	13752 KB	Output is correct
2	Correct	19 ms	13752 KB	Output is correct
3	Correct	23 ms	13752 KB	Output is correct

Subtask #7

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	13752 KB	Output is correct
2	Correct	53 ms	13752 KB	Output is correct
3	Correct	46 ms	13752 KB	Output is correct

Subtask #8

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	119 ms	13752 KB	Output is correct
2	Correct	103 ms	13752 KB	Output is correct
3	Correct	123 ms	13752 KB	Output is correct

Subtask #9

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	186 ms	13752 KB	Output is correct
2	Correct	153 ms	13752 KB	Output is correct
3	Correct	166 ms	13752 KB	Output is correct

Subtask #10

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	293 ms	13752 KB	Output is correct
2	Correct	236 ms	13752 KB	Output is correct
3	Correct	296 ms	13752 KB	Output is correct

Subtask #11

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	276 ms	13752 KB	Output is correct
2	Correct	239 ms	13752 KB	Output is correct
3	Correct	343 ms	13752 KB	Output is correct