oj.uz

Submission #29544

# Submission time Handle Problem Language Result Execution time Memory
29544 2017-07-20T05:50:56 Z 김동현(#1239) Lightning Conductor (POI11_pio) C++14
9 / 100
 256 ms 13736 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

int n;
ll h[500010], la[500010], ra[500010];

struct CHT{
	struct Cnv{ ll a, b; };
	ld val(Cnv p, ld x){
		x = max(ld(0), x - p.a);
		return x * x + p.b;
	}
	ld inv(Cnv p, ll y){
		ll s = 1, e = n;
		while(s <= e){
			ll m = (s + e) / 2;
			if(m * m >= y - p.b) e = m - 1;
			else s = m + 1;
		}
		return s + p.a;
	}
	ld cry(Cnv p, Cnv q){
		return val(p, ld(p.a * p.a + p.b - q.a * q.a - q.b) / (2 * (p.a - q.a)));
	}
	deque<Cnv> dq;
	void ini(){ dq.clear(); }
	void upd(ll a, ll b){
		Cnv cur = {a, b};
		if(!dq.empty() && dq.back().a >= cur.a) return;
		dq.push_back(cur);
	}
	ll get(ll y){
		if(dq.empty()) return 0;
		while(dq.size() > 1 && cry(dq[0], dq[1]) < y) dq.pop_front();
		return inv(dq[0], y);
	}
} C;

void f(ll *a){
	C.ini();
	for(int i = 1; i <= n; i++){
		a[i] = max(h[i], C.get(i));
		C.upd(h[i], i);
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%lld", h + i);
	f(la);
	reverse(h + 1, h + n + 1);
	f(ra);
	reverse(h + 1, h + n + 1);
	for(int i = 1; i <= n; i++) printf("%lld\n", max(la[i], ra[n + 1 - i]) - h[i]);
}

Compilation message

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

Subtask #1
0 / 9.0

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

Subtask #2
0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 13736 KB Output is correct
2 Correct 13 ms 13736 KB Output is correct
3 Incorrect 23 ms 13736 KB Output isn't correct

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 13736 KB Output is correct
2 Correct 99 ms 13736 KB Output is correct
3 Incorrect 69 ms 13736 KB Output isn't correct

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 13736 KB Output is correct
2 Correct 109 ms 13736 KB Output is correct
3 Incorrect 146 ms 13736 KB Output isn't correct

Subtask #10
0 / 9.0

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

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 13736 KB Output is correct
2 Correct 206 ms 13736 KB Output is correct
3 Incorrect 199 ms 13736 KB Output isn't correct