oj.uz

답안 #29589

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29589 2017-07-20T07:41:15 Z 김현수(#1240) Lightning Conductor (POI11_pio) C++14
100 / 100
 343 ms 13752 KB 
#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

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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