#include #include #include #include #include #include #include using ll = long long; template constexpr T INF() { return std::numeric_limits::max() / 16; } template class LiChaoTree { static std::size_t SZ(const std::size_t n) { std::size_t ans = 1; for (; ans < n; ans <<= 1) {} return ans; } public: template LiChaoTree(const InIt first, const InIt last) : size(std::distance(first, last)), half(SZ(size)), x(size), seg(half << 1, Line{0, 0, true}) { std::copy(first, last, x.begin()); } void add(const T a, const T b, const std::size_t lind, const std::size_t rind) { const Line line{a, b, false}; for (std::size_t L = lind + half, R = rind + half, sz = 1, left = lind, right = rind; L < R; L >>= 1, R >>= 1, sz <<= 1) { if (L & 1) { addLine(line, L++, left, left + sz), left += sz; } if (R & 1) { right -= sz, addLine(line, --R, right, right + sz); } } } std::pair query(std::size_t ind) const { bool exist = false; V ans = INF(); const T X = x[ind]; for (ind += half; ind > 0; ind >>= 1) { if (not seg[ind].null) { ans = (exist ? std::min(ans, seg[ind].val(X)) : seg[ind].val(X)), exist = true; } } return {exist, ans}; } private: struct Line { T a, b; bool null = true; T val(const T x) const { return a * x + b; } }; void addLine(Line l, const std::size_t ind, const std::size_t L, const std::size_t R) { const std::size_t M = (L + R) / 2; if (seg[ind].null) { return (void)(seg[ind] = l); } const T lx = x[L], rx = x[R - 1], mx = x[M]; const bool lunder = l.val(lx) < seg[ind].val(lx), munder = l.val(mx) < seg[ind].val(mx), runder = l.val(rx) < seg[ind].val(rx); if (lunder and runder) { return (void)(seg[ind] = l); } if (not lunder and not runder) { return; } if (munder) { std::swap(seg[ind], l); } return lunder != munder ? addLine(l, ind << 1, L, M) : addLine(l, ind << 1 | 1, M, R); } std::size_t size, half; std::vector x; std::vector seg; }; template class LazySeg { static std::size_t SZ(const std::size_t n) { std::size_t ans = 1; for (; ans < n; ans <<= 1) {} return ans; } public: using BaseAlgebra = Base; using ValMonoid = typename BaseAlgebra::ValMonoid; using OpMonoid = typename BaseAlgebra::OpMonoid; using T = typename BaseAlgebra::VT; using F = typename BaseAlgebra::OT; LazySeg(const std::size_t n) : size(n), half(SZ(n)), value(half << 1, ValMonoid::id()), action(half << 1, OpMonoid::id()) {} template LazySeg(const InIt first, const InIt last) : size(distance(first, last)), half(SZ(size)), value(half << 1, ValMonoid::id()), action(half << 1, OpMonoid::id()) { copy(first, last, value.begin() + half); for (std::size_t i = half - 1; i >= 1; i--) { up(i); } } T get(const std::size_t a) const { return accumulate(a, a + 1); } void set(std::size_t a, const T& val) { modify(a, a + 1, OpMonoid::id()), value[a += half] = val; while (a >>= 1) { up(a); } } T accumulate(const std::size_t L, const std::size_t R) const { auto arec = [&](auto&& self, const std::size_t index, const std::size_t left, const std::size_t right) -> T { if (L <= left and right <= R) { return value[index]; } else if (right <= L or R <= left) { return ValMonoid::id(); } else { return act(action[index], acc(self(self, index << 1, left, (left + right) >> 1), self(self, index << 1 | 1, (left + right) >> 1, right))); } }; return arec(arec, 1, 0, half); } void modify(const std::size_t L, const std::size_t R, const F& f) { auto mrec = [&](auto&& self, const std::size_t index, const std::size_t left, const std::size_t right) -> void { if (L <= left and right <= R) { this->update(index, f); } else if (right <= L or R <= left) { } else { this->update(index << 1, action[index]), this->update(index << 1 | 1, action[index]); self(self, index << 1, left, (left + right) >> 1), self(self, index << 1 | 1, (left + right) >> 1, right); this->up(index), action[index] = OpMonoid::id(); } }; mrec(mrec, 1, 0, half); } std::vector data() const { std::vector ans(size); for (std::size_t i = 0; i < size; i++) { ans[i] = get(i); } return ans; } private: void up(const std::size_t i) { value[i] = acc(value[i << 1], value[i << 1 | 1]); } void update(const std::size_t i, const F& f) { value[i] = act(f, value[i]), action[i] = compose(f, action[i]); } const std::size_t size, half; std::vector value; std::vector action; const ValMonoid acc{}; const OpMonoid compose{}; const BaseAlgebra act{}; }; template std::ostream& operator<<(std::ostream& os, const LazySeg& seg) { os << "["; for (const auto& e : seg.data()) { os << e << ","; } return (os << "]" << std::endl); } using ll = long long; std::mt19937 mt{std::random_device{}()}; template struct Sum_Plus { using VT = std::pair; struct ValMonoid { VT operator()(const VT& a, const VT& b) const { return {a.first + b.first, a.second + b.second}; } static constexpr VT id() { return {0, 0}; } }; using OT = OX; struct OpMonoid { OT operator()(const OT& f1, const OT& f2) const { return f1 + f2; } static constexpr OT id() { return 0; } }; VT operator()(const OT& f, const VT& x) const { return {x.first + x.second * f, x.second}; } }; void CodeChef() { ll N; std::size_t M; std::cin >> N >> M; std::set xs; struct Q { std::size_t t; ll u = 0, v = 0, a = 0, b = 0; }; std::vector query(M); for (std::size_t i = 0; i < M; i++) { std::cin >> query[i].t; if (query[i].t == 3) { std::cin >> query[i].u, xs.insert(query[i].u - 1), xs.insert(query[i].u), xs.insert(query[i].u + 1); } else { std::cin >> query[i].u >> query[i].v >> query[i].a >> query[i].b, xs.insert(query[i].u - 1), xs.insert(query[i].u), xs.insert(query[i].u + 1), xs.insert(query[i].v - 1), xs.insert(query[i].v), xs.insert(query[i].v + 1); } } std::map zip; std::size_t cnt = 0; std::vector::VT> v(xs.size()); for (const ll z : xs) { v[cnt].second = z, zip[z] = cnt++; } for (std::size_t i = 0; i < xs.size(); i++) { v[i].second = (i == xs.size() - 1 ? 1LL : v[i + 1].second - v[i].second); } LiChaoTree cht(xs.begin(), xs.end()); LazySeg> seg(v.begin(), v.end()); for (const auto& q : query) { if (q.t == 1) { const ll a = q.a; const ll b = q.b - a * q.u; cht.add(-a, -b, zip[q.u], zip[q.v] + 1); } else if (q.t == 2) { const std::size_t u = zip[q.u], v = zip[q.v]; seg.modify(u, u + 1, q.b); if (u < v) { seg.modify(u + 1, v + 1, q.a); } } else { const std::size_t u = zip[q.u]; const ll fee = seg.accumulate(0, u + 1).first; const auto info = cht.query(u); if (not info.first) { std::cout << "NA" << std::endl; } else { std::cout << fee - info.second << std::endl; } } } } void yukicoder() { std::size_t N; std::cin >> N; std::vector a(N + 1), x(N + 1), y(N + 1); std::vector X; for (std::size_t i = 1; i <= N; i++) { std::cin >> a[i], X.push_back(a[i]); } for (std::size_t i = 1; i <= N; i++) { std::cin >> x[i], X.push_back(x[i]); } for (std::size_t i = 1; i <= N; i++) { std::cin >> y[i]; } std::sort(X.begin(), X.end()); X.erase(std::unique(X.begin(), X.end()), X.end()); std::map zip; for (std::size_t i = 0; i < X.size(); i++) { zip[X[i]] = i; } LiChaoTree cht(X.begin(), X.end()); std::vector dp(N + 1); dp[0] = 0; cht.add(1, -x[1] + std::abs(y[1]) + dp[0], zip[x[1]], X.size()); cht.add(-1, x[1] + std::abs(y[1]) + dp[0], 0, zip[x[1]]); for (std::size_t i = 1; i <= N; i++) { dp[i] = cht.query(zip[a[i]]).second; if (i < N) { cht.add(1, -x[i + 1] + std::abs(y[i + 1]) + dp[i], zip[x[i + 1]], X.size()); cht.add(-1, x[i + 1] + std::abs(y[i + 1]) + dp[i], 0, zip[x[i + 1]]); } } std::cout << dp[N] << std::endl; } int main() { yukicoder(); return 0; }