#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5+10;
const int INF = 4e18+10;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
int K, n, MX;
int ans, MN = INF;
vector <pii> cc;
vector <int> v;
int cek(int idx){
int res = INF;
for (int x : v) {
if (x == idx) break;
int t = 0, a, b;
for (auto in : cc) {
a = abs(in.fi - idx) + abs(in.se - idx);
b = abs(in.fi - x) + abs(in.se - x);
t += min(a,b);
}
res = min(res,t);
}
return res;
int ret = 0, m = 0, c = 0;
int mn = 0;
vector <pii> vec;
for(auto in : cc){
if(in.fi <= idx && idx <= in.se){
ret += in.se-in.fi;
} else if(idx<=in.fi && idx<=in.se){
ret += in.se-idx+in.fi-idx;
} else {
int a = in.fi, b = in.se;
vec.pb({a+b-idx, 0});
vec.pb({a, 1});
vec.pb({b, 1});
c += 2*idx-a-b;
}
}
mn = c;
sort(vec.begin(), vec.end());
for(int i=0; i<vec.size(); i++){
int nw = vec[i].fi;
/*while(i+1<vec.size() && vec[i+1].fi == vec[i].fi){
// upd i
if(vec[i].se){
m += 2;
c += -2*nw;
} else {
m -= 2;
c += 2*nw;
}
i++;
}*/
// upd i
if(vec[i].se){
m += 2;
c += -2*nw;
} else {
m -= 2;
c += 2*nw;
}
mn = min(mn, m*nw+c);
}
return ret+mn;
// <a[i]+b[i]-idx,<-2,2*a[i]+2*b[i]-2*idx>>
// <a[i],<2,-2*a[i]>>
// <b[i],<2,-2*b[i]>>
// <a[i]+b[i]-idx,0>
// <a[i],1>
// <b[i],1>
// idx-b[i] <= a[i]-x
// x <= a[i]+b[i]-idx
// 2*idx-a[i]-b[i]
// a[i]+b[i]-idx <= x <= a[i]
// a[i]+b[i]-2x
// a[i] <= x <= b[i]
// b[i]-a[i]
// b[i] <= x
// 2x-a[i]-b[i]
// <a[i],i>
// <b[i],i>
}
void solve(){
cin >> K >> n;
if(K==1){
// exit(0);
vec.pb(-1);
for(int i=1; i<=n; i++){
char x, y; int a, b;
cin >> x >> a >> y >> b; a++; b++;
if(x==y) ans += abs(a-b);
else {
vec.pb(a); vec.pb(b);
}
}
sort(vec.begin(), vec.end());
int MN = INF, siz = vec.size()-1;
for(int i=1; i<=siz; i++){
ans += abs(vec[(siz+1)/2]-vec[i]);
}
ans += siz/2;
cout << ans << '\n';
exit(0);
}
v.pb(-1);
for(int i=1; i<=n; i++){
char x, y; int a, b;
cin >> x >> a >> y >> b; a++; b++;
if(x==y){
ans += abs(a-b); continue;
}
if(a > b) swap(a, b);
cc.pb({a, b});
v.pb(a); v.pb(b);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
int l=1, r=v.size()-1, mid1=0, mid2=0;
while(r-l+1 >= 410){
mid1 = (l+l+r)/3; mid2 = (l+r+r+2)/3;
int num1 = cek(v[mid1]), num2 = cek(v[mid2]);
// cout << mid1 << " " << mid2 << " " << cek(mid1) << " " << cek(mid2) << endl;
MN = min(MN, min(num1, num2));
if(num1 < num2) r = mid2;
else l = mid1;
}
// cout << l << ' ' << r << " lr\n";
for(int mid=l; mid<=r; mid++){
// cout << mid << " " << cek(mid) << endl;
MN = min(MN, cek(v[mid]));
}
cout << ans + MN + (int)cc.size() << '\n';
ans = 0; MN = INF;
cc.clear(); v.clear();
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// int T = 1;
// while(T--){
// solve();
// }
solve();
}
Compilation message
bridge.cpp: In function 'long long int cek(long long int)':
bridge.cpp:51:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i=0; i<vec.size(); i++){
| ~^~~~~~~~~~~
bridge.cpp: In function 'void solve()':
bridge.cpp:105:3: error: 'vec' was not declared in this scope
105 | vec.pb(-1);
| ^~~
bridge.cpp:116:7: warning: unused variable 'MN' [-Wunused-variable]
116 | int MN = INF, siz = vec.size()-1;
| ^~
