#include "wiring.h" #include <bits/stdc++.h> using namespace std; long long min_total_length(vector<int> r, vector<int> b) { int N = r.size() + b.size(); int ridx = 0, bidx = 0; vector<int> pos = {0}, col = {0}; while (ridx < r.size() || bidx < b.size()) { if (bidx == b.size()) { pos.push_back(r[ridx]); col.push_back(0); ridx++; } else if (ridx == r.size()) { pos.push_back(b[bidx]); col.push_back(1); bidx++; } else if (r[ridx] < b[bidx]) { pos.push_back(r[ridx]); col.push_back(0); ridx++; } else { pos.push_back(b[bidx]); col.push_back(1); bidx++; } } vector<pair<int, int>> seg; for (int i = 1; i <= N; ) { int j = i; while (j <= N && col[i] == col[j]) { j++; } seg.push_back(make_pair(i, j - 1)); i = j; } vector<long long> pre(N + 1); vector<long long> suf(N + 1); for (int i = 0; i < seg.size(); i++) { int lb = seg[i].first, rb = seg[i].second; for (int j = rb - 1; j >= lb; j--) { suf[j] = suf[j + 1] + (pos[rb] - pos[j]); } for (int j = lb + 1; j <= rb; j++) { pre[j] = pre[j - 1] + (pos[j] - pos[lb]); } } vector<long long> dp(N + 1, (long long)1e18); dp[0] = 0; for (int sid = 1; sid < seg.size(); sid++) { int clb = seg[sid].first, crb = seg[sid].second; int plb = seg[sid - 1].first, prb = seg[sid - 1].second; for (int c = clb; c <= crb; c++) { auto calc = [&] (int p) { int psz = prb - p + 1; int csz = c - clb + 1; long long cost = 0; cost += suf[p] + pre[c]; cost += (long long)(pos[clb] - pos[prb]) * max(psz, csz); return min(dp[p - 1], dp[p]) + cost; }; if (sid == 1) { dp[c] = calc(plb); } else { int ll = plb, rr = prb + 1; while (ll + 1 < rr) { int mm = ll + (rr - ll) / 2; if (calc(mm) - calc(mm - 1) < 0) { ll = mm; } else { rr = mm; } } dp[c] = calc(ll); } } } return dp[N]; }