# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
29536 | 2017-07-20T05:40:16 Z | 김동현(#1239) | Lightning Conductor (POI11_pio) | C++14 | 219 ms | 13752 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){ return sqrt(ld(y - p.b)) + 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 ll(inv(dq[0], y) + ld(1) - ld(1e-9)); } } 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 13752 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 13752 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13752 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 13752 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 19 ms | 13752 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 13752 KB | Output is correct |
2 | Correct | 16 ms | 13752 KB | Output is correct |
3 | Incorrect | 26 ms | 13752 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 29 ms | 13752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 83 ms | 13752 KB | Output is correct |
2 | Correct | 63 ms | 13752 KB | Output is correct |
3 | Incorrect | 76 ms | 13752 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 119 ms | 13752 KB | Output is correct |
2 | Correct | 129 ms | 13752 KB | Output is correct |
3 | Incorrect | 86 ms | 13752 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 219 ms | 13752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 219 ms | 13752 KB | Output is correct |
2 | Correct | 129 ms | 13752 KB | Output is correct |
3 | Incorrect | 166 ms | 13752 KB | Output isn't correct |