oj.uz

Submission #29597

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

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

struct CHT{
	struct Cnv{ ll a, b; };
	int cinv(Cnv p, Cnv q, ll y){
		lll A = y - p.b, B = p.a, C = y - q.b, D = q.a;
		if(A <= C && D >= B) return 1;
		if(A >= C && D <= B) return 0;
		lll E = A + C - (B - D) * (B - D);
		if(A >= C){
			if(E <= 0) return 1;
			return E * E <= 4 * A * C;
		}
		else{
			if(E < 0) return 0;
			return E * E >= 4 * A * C;
		}
	}
	ll iinv(Cnv p, ll y){
		ll s = 0, e = 710;
		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 cr(Cnv p, Cnv q){
		return ld(p.a * p.a + p.b - q.a * q.a - q.b) / (2 * (p.a - q.a));
	}
	vector<Cnv> v;
	int f;
	void ini(){ v.clear(); f = 0; }
	void upd(ll a, ll b){
		Cnv cur = {a, b};
		if(v.size() > f && v.back().a >= cur.a) return;
		while(v.size() > f && iinv(v.back(), cur.b) <= cur.a) v.pop_back();
		while(v.size() > f + 1 &&
			cr(v.back(), cur) <= cr(v[int(v.size()) - 2], cur)) v.pop_back();
		v.push_back(cur);
	}
	ll get(ll y){
		if(f >= v.size()) return 0;
		while(int(v.size()) > f + 1 && cinv(v[f], v[f + 1], y)) f++;
		return iinv(v[f], 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 member function 'void CHT::upd(ll, ll)':
pio.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(v.size() > f && v.back().a >= cur.a) return;
               ^
pio.cpp:44:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(v.size() > f && iinv(v.back(), cur.b) <= cur.a) v.pop_back();
                  ^
pio.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(v.size() > f + 1 &&
                  ^
pio.cpp: In member function 'll CHT::get(ll)':
pio.cpp:50:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(f >= v.size()) return 0;
        ^
pio.cpp: In function 'int main()':
pio.cpp:65:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
pio.cpp:66: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
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13736 KB Output is correct
2 Correct 13 ms 13736 KB Output is correct
3 Correct 19 ms 13736 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13736 KB Output is correct
2 Correct 36 ms 13736 KB Output is correct
3 Correct 59 ms 13736 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 13736 KB Output is correct
2 Correct 66 ms 13736 KB Output is correct
3 Correct 96 ms 13736 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 13736 KB Output is correct
2 Correct 99 ms 13736 KB Output is correct
3 Correct 129 ms 13736 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 13736 KB Output is correct
2 Correct 193 ms 13736 KB Output is correct
3 Correct 179 ms 13736 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 13736 KB Output is correct
2 Correct 209 ms 13736 KB Output is correct
3 Correct 183 ms 13736 KB Output is correct