# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
29557 | 2017-07-20T06:07:19 Z | 김동현(#1239) | Lightning Conductor (POI11_pio) | C++14 | 223 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 inv(Cnv p, ll y){ return sqrt(ld(y - p.b)) + p.a; } 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; } deque<Cnv> dq; int r; void ini(){ dq.clear(); r = 0; } void upd(ll a, ll b){ Cnv cur = {a, b}; if(!dq.empty() && dq.back().a >= cur.a) return; while(dq.size() > 1 && inv(dq[r - 1], cur.b) <= inv(dq[r - 2], cur.b)){ dq.pop_back(); r--; } dq.push_back(cur); r++; } ll get(ll y){ if(dq.empty()) return 0; while(dq.size() > 1 && inv(dq[0], y) <= inv(dq[1], y)){ dq.pop_front(); r--; } return iinv(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 | Correct | 0 ms | 13752 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13752 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13752 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 13752 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 13752 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 13752 KB | Output is correct |
2 | Correct | 13 ms | 13752 KB | Output is correct |
3 | Incorrect | 19 ms | 13752 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 36 ms | 13752 KB | Output is correct |
2 | Correct | 33 ms | 13752 KB | Output is correct |
3 | Incorrect | 36 ms | 13752 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 66 ms | 13752 KB | Output is correct |
2 | Correct | 66 ms | 13752 KB | Output is correct |
3 | Incorrect | 83 ms | 13752 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 139 ms | 13752 KB | Output is correct |
2 | Correct | 83 ms | 13752 KB | Output is correct |
3 | Incorrect | 153 ms | 13752 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 223 ms | 13752 KB | Output is correct |
2 | Correct | 129 ms | 13752 KB | Output is correct |
3 | Incorrect | 143 ms | 13752 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 199 ms | 13752 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |