#include // clang-format off std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;} std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<std::ostream &operator<<(std::ostream&os,const std::pair&x){return os<<"("<std::ostream &operator<<(std::ostream&os,const std::vector&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<std::ostream &operator<<(std::ostream&os,const std::set&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<std::ostream&operator<<(std::ostream &os,const std::array &arr) {os<<'['<void print(std::ostream&os,const Tup &x,std::index_sequence){(void)(int[]){(os<(x)<<", ",0)...};} templatestd::ostream &operator<<(std::ostream&os,const std::tuple &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence());return os<(x)<<")";} const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m"; #define func_LINE_FILE NORMAL_FAINT<<" in "<"< auto compress(std::vector &v) { return std::sort(v.begin(), v.end()), v.erase(std::unique(v.begin(), v.end()), v.end()), [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); }; } template class PiecewiseLinearConvexfunction { public: using i64= long long; using i128= __int128_t; using node_id= std::int_least32_t; static constexpr i64 INF= 1ll << 60; template static inline std::string str(Int x) { if (x >= INF) return "inf"; if (x <= -INF) return "-inf"; std::stringstream ss; ss << x; return ss.str(); } struct Node { node_id ch[2], par; i64 dx, slope, laz, x; i128 y; }; friend std::ostream &operator<<(std::ostream &os, Node *t) { if (!t) return os << "nullptr"; return os << "{dx:" << str(t->dx) << ",slope:" << str(t->slope) << ",x:" << str(t->x) << ",y:" << str(t->y) << ",laz:" << str(t->laz) << "}"; } // friend std::ostream &operator<<(std::ostream &os, Node *t) { // if (!t) return os << "nullptr"; // return os << "{dx:" << str(t->dx) << ",slope:" << str(t->slope) << "}"; // } static inline Node ns[NODE_SIZE]; static inline node_id ni= 1; static inline void clear() { ni= 1; } static inline void propagate(node_id i, i64 a) { if (i) ns[i].slope+= a, ns[i].laz+= a, ns[i].y+= i128(a) * ns[i].x; } static inline void push(node_id i) { if (ns[i].laz) propagate(ns[i].ch[0], ns[i].laz), propagate(ns[i].ch[1], ns[i].laz), ns[i].laz= 0; } static inline void pushup(node_id i) { ns[i].x= ns[i].dx, ns[i].y= i128(ns[i].slope) * ns[i].dx; if (int j= ns[i].ch[0]; j) ns[i].x+= ns[j].x, ns[i].y+= ns[j].y; if (int j= ns[i].ch[1]; j) ns[i].x+= ns[j].x, ns[i].y+= ns[j].y; } static inline int dir(node_id i) { return ns[ns[i].par].ch[1] == i; } static inline void rot(node_id i) { node_id p= ns[i].par; int d= dir(i); if ((ns[p].ch[d]= ns[i].ch[!d])) ns[ns[p].ch[d]].par= p; ns[i].ch[!d]= p; if ((ns[i].par= ns[p].par)) ns[ns[p].par].ch[dir(p)]= i; ns[p].par= i; } static inline void splay(node_id i) { for (node_id p= ns[i].par; p; p= ns[i].par) { if (node_id pp= ns[p].par; pp) rot(dir(i) == dir(p) ? p : i), rot(i), pushup(pp), pushup(p); else rot(i), pushup(p); } pushup(i); } static inline void slope_search(node_id &i, i64 k) { for (node_id s;; i= s) { push(i); i64 tmp= ns[i].slope; if (tmp == k) break; if (s= ns[i].ch[tmp < k]; !s) break; } splay(i); } static inline void x_search(node_id &i, i64 x) { for (bool c;; i= ns[i].ch[c]) { push(i); i64 l= ns[i].ch[0] ? ns[ns[i].ch[0]].x : 0, r= l + ns[i].dx; if (l <= x && x <= r) return splay(i); if ((c= (r < x))) x-= r; } } static inline void debugoutput(node_id i, int d) { if (!i) return; push(i); debugoutput(ns[i].ch[0], d + 1); for (int i= 0; i < d; ++i) std::cerr << " "; std::cerr << "■ " << (i ? ns + i : nullptr) << '\n'; debugoutput(ns[i].ch[1], d + 1); } node_id root; i64 lb; i128 lby; public: void debugoutput() { debugoutput(root, 0); } // f(x) := 0 PiecewiseLinearConvexfunction(): lb(-INF * 2), lby(0), root(ni++) { ns[root].x= ns[root].dx= INF * 4, ns[root].par= ns[root].ch[0]= ns[root].ch[1]= ns[root].slope= ns[root].laz= ns[root].y= 0; } // f(x) := 0 if x == 0 else ∞ PiecewiseLinearConvexfunction(int a): lb(0), lby(0), root(ni++) { ns[root].x= ns[root].dx= ns[root].par= ns[root].ch[0]= ns[root].ch[1]= ns[root].slope= ns[root].laz= ns[root].y= 0; } // f(x) + c void add_const(i64 c) { lby+= c; } // f(x) + ax+c void add_linear(i64 a, i64 c= 0) { lby+= i128(a) * lb + c, propagate(root, a); } // f(x-a) void shift(i64 a) { lb+= a; } // f(x) + a * max{x, 0} void add_relu(i64 a) { if (0 <= lb) return add_linear(a); if (lb + ns[root].x <= 0) return; x_search(root, -lb); i64 l= ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0, r= l + ns[root].dx; if (l == -lb) { node_id i= ns[root].ch[0]; ns[root].ch[0]= 0; propagate(root, a); push(root); ns[root].ch[0]= i; } else if (r == -lb) { propagate(ns[root].ch[1], a); } else { node_id i= ni++; ns[i].ch[0]= ns[i].laz= 0; ns[i].slope= ns[root].slope; ns[i].dx= r + lb; if ((ns[i].ch[1]= ns[root].ch[1])) ns[ns[i].ch[1]].par= i; pushup(i), propagate(i, a); ns[root].ch[1]= i, ns[i].par= root; ns[root].dx= -lb - l, pushup(root); } } // f(x) + a * min{x,0} + b * max{x,0} void add_ax_bx(i64 a, i64 b) { add_linear(a), add_relu(b - a); } // f(x) + a * min{x-c,0} + b * max{x-c,0} void add_ax_bx_c(i64 a, i64 b, i64 c) { shift(-c), add_ax_bx(a, b), shift(c); } // f(x) + a * |x-c| void add_abs(i64 a, i64 c) { add_ax_bx_c(-a, a, c); } // min_{y<=x} f(y) void cumulative_chmin() { slope_search(root, 0); if (ns[root].slope < 0) { if (!ns[root].ch[1]) ns[root].ch[1]= ni++; node_id i= ns[root].ch[1]; ns[i].x= ns[i].dx= INF * 2, ns[i].slope= ns[i].ch[0]= ns[i].ch[1]= ns[i].laz= ns[i].y= 0, ns[i].par= root; } else ns[root].ch[1]= 0, ns[root].dx= INF * 2, ns[root].slope= 0, pushup(root); } i128 eval(i64 x) { if (x-= lb; x < 0 || ns[root].x < x) return INF; x_search(root, x); if (int i= ns[root].ch[0]; i) return lby + ns[i].y + i128(x - ns[i].x) * ns[root].slope; return lby + i128(x) * ns[root].slope; } std::array argmin() { slope_search(root, 0); i64 l= lb + (ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0), r= l + ns[root].dx; if (ns[root].slope == 0) return {l, r}; return ns[root].slope < 0 ? std::array{r, r} : std::array{l, l}; } i128 min() { return eval(argmin()[0]); } }; using namespace std; // https://atcoder.jp/contests/abc127/tasks/abc127_f namespace ABC127F { signed main() { cin.tie(0); ios::sync_with_stdio(0); int Q; cin >> Q; PiecewiseLinearConvexfunction f; while (Q--) { // debug(Q); int op; cin >> op; if (op == 1) { int a, b; cin >> a >> b; f.add_abs(1, a); f.add_const(b); } else { cout << f.argmin()[0] << " " << f.min() << '\n'; } // f.debugoutput(); } // f.debugoutput(); // debug(f.lb); // debug(f.lby); return 0; } } // https://atcoder.jp/contests/kupc2016/tasks/kupc2016_h namespace atcoder_kupc2016_h { signed main() { cin.tie(0); ios::sync_with_stdio(0); int N; cin >> N; long long A[N], B[N]; for (int i= 0; i < N; ++i) cin >> A[i]; for (int i= 0; i < N; ++i) cin >> B[i]; PiecewiseLinearConvexfunction f(1); for (int i= 0; i < N; ++i) { f.cumulative_chmin(); f.shift(B[i] - A[i]); f.add_abs(1, 0); } cout << f.eval(0) << '\n'; return 0; } } // https://yukicoder.me/problems/no/1467 namespace yukicoder1467 { signed main() { cin.tie(0); ios::sync_with_stdio(0); using PLCF= PiecewiseLinearConvexfunction<>; int M, N; cin >> M >> N; long long A[M], B[N]; for (int i= 0; i < M; ++i) cin >> A[i]; for (int j= 0; j < N; ++j) cin >> B[j]; vector vec(A, A + M); for (int j= 0; j < N; ++j) vec.push_back(B[j]); auto id= compress(vec); int n= vec.size(); vector a(n), b(n); for (int i= 0; i < M; ++i) ++a[id(A[i])]; for (int j= 0; j < N; ++j) ++b[id(B[j])]; for (int k= 1; k <= M; ++k) { PLCF f(1); for (int i= 0; i < n; ++i) { f.cumulative_chmin(); f.shift(a[i] - b[i] * k); if (i < n - 1) f.add_abs(vec[i + 1] - vec[i], 0); } cout << f.eval(0) << '\n'; PLCF::clear(); } return 0; } } signed main() { cin.tie(0); ios::sync_with_stdio(0); // ABC127F::main(); // atcoder_kupc2016_h::main(); yukicoder1467::main(); return 0; }