oj.uz

Submission #29588

# Submission time Handle Problem Language Result Execution time Memory
29588 2017-07-20T07:37:19 Z 김현수(#1240) Lightning Conductor (POI11_pio) C++14
18 / 100
 136 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.Y, 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;}
		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:48:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
pio.cpp:49: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
0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 13752 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 13752 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 13752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 13752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 13752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 123 ms 13752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 13752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -