# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
29590 | 2017-07-20T07:41:24 Z | 김동현(#1239) | Lightning Conductor (POI11_pio) | C++14 | 199 ms | 13740 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; } 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 && cinv(v.back(), v[int(v.size()) - 2], cur.b)) 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13740 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13740 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13740 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 13740 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 13740 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 13740 KB | Output is correct |
2 | Correct | 16 ms | 13740 KB | Output is correct |
3 | Incorrect | 19 ms | 13740 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 39 ms | 13740 KB | Output is correct |
2 | Correct | 26 ms | 13740 KB | Output is correct |
3 | Incorrect | 26 ms | 13740 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 69 ms | 13740 KB | Output is correct |
2 | Correct | 59 ms | 13740 KB | Output is correct |
3 | Incorrect | 89 ms | 13740 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 129 ms | 13740 KB | Output is correct |
2 | Correct | 96 ms | 13740 KB | Output is correct |
3 | Incorrect | 106 ms | 13740 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 199 ms | 13740 KB | Output is correct |
2 | Correct | 136 ms | 13740 KB | Output is correct |
3 | Incorrect | 189 ms | 13740 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 173 ms | 13740 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |