# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
29548 | 2017-07-20T05:55:40 Z | 김동현(#1239) | Lightning Conductor (POI11_pio) | C++14 | 239 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 inv(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; } 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 && inv(dq[0], y) <= inv(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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 13736 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13736 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 13736 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 13736 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 13736 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 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 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 43 ms | 13736 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 93 ms | 13736 KB | Output is correct |
2 | Correct | 69 ms | 13736 KB | Output is correct |
3 | Incorrect | 93 ms | 13736 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 126 ms | 13736 KB | Output is correct |
2 | Correct | 133 ms | 13736 KB | Output is correct |
3 | Incorrect | 149 ms | 13736 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 239 ms | 13736 KB | Output is correct |
2 | Correct | 196 ms | 13736 KB | Output is correct |
3 | Incorrect | 203 ms | 13736 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 176 ms | 13736 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |