#pragma GCC optimize("Ofast,unroll-loops") #include "wiring.h" #include <bits/stdc++.h> //#define int long long #define ll long long #define ull unsigned long long #define down cout<<'\n'; #define debug cout<<" cucuucucuuu",down #define modwwe int t;cin>>t; while(t--) #define bit(i,j) (i>>j&1) #define sobit(a) __builtin_popcountll(a) #define task2 "top1apio" #define task "test" #define fin(x) freopen(x".inp","r",stdin) #define fou(x) freopen(x".out","w",stdout) #define pb push_back #define mask(k) (1ll<<k) #define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; using namespace std; #define getchar_unlocked getchar mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); using i128 = __int128; int rand(int l, int r) { return uniform_int_distribution<int>(l, r)(rd); } void phongbeo(); const ll inf = 1e17; const int mod2 = 998244353; //const ll base=67; ll n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center; ll i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, root,q; ll el = 19; struct ib { int a,b; }; vector<ib> v,vc; ll dp[200007],pre[200007],suff[200007]; vector<ll> hihi[200007]; stack<int> vl; bool cmp(ib a,ib b) { return a.a<b.a; } ll min_total_length(vector<int> A,vector<int> B) { for(auto x:A)v.pb({x,0}); for(auto x:B)v.pb({x,1}); n=v.size(); sort(v.begin(),v.end(),cmp); s2=1; vl.push(v[0].a); dem=0; for(int i=1; i<v.size(); i++) { if(v[i].b!=v[i-1].b) { while(!vl.empty())hihi[dem].pb(vl.top()),vl.pop(); reverse(hihi[dem].begin(),hihi[dem].end()); dem++; vc.pb({s2,v[i-1].b}); s2=0; } vl.push(v[i].a); s2++; } vc.pb({s2,v.back().b}); while(!vl.empty())hihi[dem].pb(vl.top()),vl.pop(); reverse(hihi[dem].begin(),hihi[dem].end()); ///x con ///y con /** case1: x<=y { cost(y)-cost(x)-last(x)*(y-x) =>cost(y)-last(x)*y-(cost(x)-lats(x)*x) } case2: x>y { cost(y)-cost(x)+begin(y)*(x-y) =>(cost(y)-begin(y)*y)-(cost(x)-begin(y)*x) } */ for(int i=0; i<=n; i++) dp[i]=inf; dp[0]=0; for(int i=1; i<=dem; i++) { s2=0; int sz=hihi[i-1].size(); for(int j=0; j<=hihi[i].size(); j++) pre[j]=-inf,suff[j]=-inf; for(int j=hihi[i-1].size()-1; j>=0; --j) { pre[sz-(j+1)]=s2-hihi[i-1].back()*(sz-(j+1))-dp[j+1]; suff[sz-(j+1)]=s2-hihi[i][0]*(sz-(j+1))-dp[j+1]; s2+=hihi[i-1][j]; } suff[sz]=s2-hihi[i][0]*sz-dp[0]; pre[sz]=s2-hihi[i-1].back()*sz-dp[0]; for(int j=1; j<=hihi[i].size(); j++) pre[j]=max(pre[j],pre[j-1]); for(int j=hihi[i-1].size()-1; j>=1; --j) suff[j]=max(suff[j],suff[j+1]); s2=0; dp[0]=dp[sz]; for(int j=0; j<hihi[i].size(); j++) { s2=s2+hihi[i][j]; dp[j+1]=s2-hihi[i-1].back()*(j+1)-pre[j+1]; if(j+1<=hihi[i-1].size()) dp[j+1]=min(dp[j+1],s2-hihi[i][0]*(j+1)-suff[j+1]); } } return dp[hihi[dem].size()]; }

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:63:20: warning: narrowing conversion of 's2' from 'long long int' to 'int' [-Wnarrowing]
   63 |             vc.pb({s2,v[i-1].b});
      |                    ^~
wiring.cpp:69:12: warning: narrowing conversion of 's2' from 'long long int' to 'int' [-Wnarrowing]
   69 |     vc.pb({s2,v.back().b});
      |            ^~