# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
34878 | 2017-11-16T11:23:15 Z | szawinis | Lightning Conductor (POI11_pio) | C++14 | 1000 ms | 6192 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 5e5+1; const ll is_query = -(1LL<<62); struct Line { ll m, b; mutable function<const Line*()> succ; bool operator<(const Line& rhs) const { if (rhs.b != is_query) return m < rhs.m; const Line* s = succ(); if (!s) return 0; ll x = rhs.m; return b - s->b < (s->m - m) * x; } }; struct HullDynamic : public multiset<Line> { // will maintain upper hull for maximum bool bad(iterator y) { auto z = next(y); if (y == begin()) { if (z == end()) return 0; return y->m == z->m && y->b <= z->b; } auto x = prev(y); if (z == end()) return y->m == x->m && y->b <= x->b; return (x->b - y->b)*(z->m - y->m) >= (y->b - z->b)*(y->m - x->m); } void update(ll m, ll b) { auto y = insert({ m, b }); y->succ = [=] { return next(y) == end() ? 0 : &*next(y); }; if (bad(y)) { erase(y); return; } while (next(y) != end() && bad(next(y))) erase(next(y)); while (y != begin() && bad(prev(y))) erase(prev(y)); } ll query(ll x) { auto l = *lower_bound((Line) { x, is_query }); return l.m * x + l.b; } } dp; int n, h[N], res[N]; void solve() { dp.clear(); dp.update(2*h[0], -1ll*h[0]*h[0]); int mx = h[0]; for(int i = 1, x = 0; i < n; i++) { while(x < mx || 1ll*x*x - i < dp.query(x)) ++x; res[i] = max(x, res[i]); mx = max(mx, h[i]); dp.update(2*h[i], -1ll*h[i]*h[i] - i); } } int main() { scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &h[i]); solve(); reverse(h, h+n); reverse(res, res+n); solve(); reverse(h, h+n); reverse(res, res+n); for(int i = 0; i < n; i++) printf("%d\n", max(res[i] - h[i], 0)); } // h[j] <= x - sqrt(i - j) // x - h[j] >= sqrt(i - j) // x^2 - 2xh[j] + h[j]^2 >= i - j // x^2 - i >= 2xh[j] - h[j]^2 - j // // x^2 - 2xh[j] + h[j]^2 >= j - i // x^2 + i >= 2xh[j] - h[j]^2 + j
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 5928 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 5928 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 5928 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 986 ms | 5928 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 996 ms | 5928 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 329 ms | 6060 KB | Output is correct |
2 | Correct | 26 ms | 5928 KB | Output is correct |
3 | Correct | 76 ms | 6192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 853 ms | 5928 KB | Output is correct |
2 | Correct | 563 ms | 5928 KB | Output is correct |
3 | Execution timed out | 1000 ms | 6192 KB | Execution timed out |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1000 ms | 5928 KB | Execution timed out |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1000 ms | 5928 KB | Execution timed out |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1000 ms | 5928 KB | Execution timed out |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1000 ms | 5928 KB | Execution timed out |
2 | Halted | 0 ms | 0 KB | - |