#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5;
const ll inf = 2e9;
vector <ll> a;
vector <ll> c;
struct p{
ll nr,tip;
}v[2*N];
ll dp[2*N];
ll ps[2*N + 1];
ll sum(ll l,ll r){
return ps[r + 1] - ps[l];
}
ll min_total_length(vector <ll> r,vector <ll> b){
ll n = 0;
for(ll i = 0;i < r.size();i++){
v[n++] = {r[i],0};
}
for(ll i = 0;i < b.size();i++){
v[n++] = {b[i],1};
}
sort(v,v + n,[&](p a,p b){
return a.nr < b.nr;
});
for(ll i = 0;i < n;i++){
ps[i + 1] = ps[i] + v[i].nr;
dp[i] = inf;
}
ll i = 0,p = -1;
while(i < n){
ll nxt = i;
while(nxt < n - 1 && v[i].tip == v[nxt + 1].tip)nxt++;
if(p != -1){
///p index of first red
///i index of first blue
///nxt index of last blue
///case 1: right side bigger
ll l = i - 1;
ll r = i;
ll cross = (v[i].nr - v[i - 1].nr);
ll minn = inf;
while(l >= p && r <= nxt){
minn = min(minn,(l == 0?0:dp[l - 1]) + ((i - l)*v[i - 1].nr - sum(l,i - 1)));
//cout<<minn<<' '<<(r - i + 1)*cross<<' '<<sum(i,r)<<' '<<'\n';
dp[r] = min(dp[r],(r - i + 1)*cross + (sum(i,r) - v[i].nr*(r - i + 1)) + minn);
l--;r++;
}
while(r <= nxt){
//cout<<minn<<' '<<(r - i + 1)*cross<<' '<<sum(i,r)<<' '<<'\n';
dp[r] = min(dp[r],(r - i + 1)*cross + (sum(i,r) - v[i].nr*(r - i + 1)) + minn);
r++;
}
///case 2:left side bigger
l = p;
r = nxt;
minn = inf;
while(i - 1 - l > r - i){
minn = min(minn,(l == 0?0:dp[l - 1]) + (i - l)*cross + v[i - 1].nr*(i - l) - sum(l,i - 1));
l++;
}
while(i - 1 - l < r - i){
r--;
}
while(l < i && r > i - 1){
minn = min(minn,(l == 0?0:dp[l - 1]) + (i - l)*cross + v[i - 1].nr*(i - l) - sum(l,i - 1));
//cout<<r<<' '<<minn<<' '<<sum(i,r)<<' '<<v[i].nr*(r - i + 1)<<'\n';
dp[r] = min(dp[r],sum(i,r) - v[i].nr*(r - i + 1) + minn);
l++;
r--;
}
for(ll j = 0;j < n;j++){
cout<<dp[j]<<' ';
}
cout<<'\n';
}
p = i;
i = nxt;
i++;
}
cout<<dp[n - 1]<<'\n';
}
/**
int main(){
ll n,m;
cin>>n>>m;
a.resize(n);
c.resize(m);
for(ll i = 0;i < n;i++){
cin>>a[i];
}
for(ll i = 0;i < m;i++){
cin>>c[i];
}
min_total_length(a,c);
return 0;
}
**/
/**
4 5
1 2 3 7
0 4 5 9 10
**/
Compilation message
wiring.cpp: In function 'll min_total_length(std::vector<long long int>, std::vector<long long int>)':
wiring.cpp:18:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(ll i = 0;i < r.size();i++){
| ~~^~~~~~~~~~
wiring.cpp:21:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(ll i = 0;i < b.size();i++){
| ~~^~~~~~~~~~
wiring.cpp:84:1: warning: no return statement in function returning non-void [-Wreturn-type]
84 | }
| ^
/usr/bin/ld: /tmp/cchhJ80z.o: in function `main':
grader.cpp:(.text.startup+0x23a): undefined reference to `min_total_length(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
