// 嘘を実装してました 逃亡 #include "template/template.hpp" // #include "segment-tree/lazy-segment-tree.hpp" using namespace Nyaan; struct D { double a, b, c; D() : a(0), b(0), c(0) {} D(double _a, double _b, double _c) : a(_a), b(_b), c(_c) {} double eval(double x) { return a / x + b * x + c; } }; struct E { int f; double a, b, c; E() : f(-1), a(0), b(0), c(0) {} E(int _f, double _a, double _b, double _c) : f(_f), a(_a), b(_b), c(_c) {} bool operator==(const E& rhs) { return f == rhs.f; } }; // range add range update // 二分探索は手元でやる void q() { auto f = [&](D a, D) -> D { return a; }; auto g = [&](D a, E b) -> D { if (b.f == -1) return a; if (b.f == 1) { a.a += b.a, a.b += b.b, a.c += b.c; return a; } if (b.f == 2) { a.a = b.a, a.b = b.b, a.c = b.c; return a; } exit(1); }; auto h = [&](E a, E b) -> E { if (b.f == -1) return a; if (b.f == 1) { if (a.f == -1) return b; a.a += b.a, a.b += b.b, a.c += b.c; return a; } if (b.f == 2) { return b; } exit(1); }; D ti{}; E ei{}; inl(N); vl A(N), B(N); in(A, B); V> p; p.emplace_back(1, -1); rep(i, N) p.emplace_back(sqrt(A[i] / B[i]), i); sort(all(p)); vi inv(N, -1); int th = -1; rep(i, sz(p)) { if (p[i].se != -1) inv[p[i].se] = i; if (p[i].se == -1) th = p[i].se; } trc(p); V init(sz(p)); LazySegmentTree seg(init, f, g, h, ti, ei); repr(i, N) { { int f = 1; double a = A[i]; double b = B[i]; double c = 0; seg.update(0, sz(p), E{f, a, b, c}); } int L = -1, R = sz(p); while (L + 2 < R) { int i1 = (L + L + R) / 3; int i2 = (L + R + R) / 3; double x1 = p[i1].fi; double x2 = p[i2].fi; double y1 = seg.get_val(i1).eval(x1); double y2 = seg.get_val(i2).eval(x2); if (y1 < y2) { R = i2; } else { L = i1; } } int key = (L + R) / 2; double x = p[key].fi; D data = seg.get_val(key); double val = data.eval(x); seg.update(0, key + 1, E{2, 0., 0., val}); } { int L = th - 1, R = sz(p); while (L + 2 < R) { int i1 = (L + L + R) / 3; int i2 = (L + R + R) / 3; double x1 = p[i1].fi; double x2 = p[i2].fi; double y1 = seg.get_val(i1).eval(x1); double y2 = seg.get_val(i2).eval(x2); if (y1 < y2) { R = i2; } else { L = i1; } } int key = (L + R) / 2; double x = p[key].fi; D data = seg.get_val(key); double val = data.eval(x); trc(key, x, val); out(val); } } void Nyaan::solve() { int T = 1; // in(T); while (T--) q(); }