#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 21, MOD = (int)1e9+7;
#define int ll
int n,k;
ll res = 0;
array<int,2> a[N];
ll L[N],R[N];
vector<pair<int,int>> sc;
void prec(){
for(int i = 1;i <= n;i++){
sc.push_back({a[i][0],0});
sc.push_back({a[i][1],1});
}
sort(sc.begin(),sc.end());
ll sum = 0,col = 0;
for(int i = 0;i < (int)sc.size();i++){
L[i] = (sc[i].first * 1ll * col) - sum;
if(sc[i].second == 1){
col++;
sum += sc[i].first;
}
}
col = sum =0 ;
for(int i = (int)sc.size() - 1;i >= 0;i--){
R[i] = sum - (sc[i].first * 1ll * col);
if(sc[i].second == 0){
col++;
sum += sc[i].first;
}
}
}
ll solve(){
if(!n) return 0;
ll res = 1e18;
for(int i = 0;i < (int)sc.size();i++){
res = min(res,2*(L[i] + R[i]));
}
return res;
}
ll calc(int l,int r){
ll sum = 0;
for(int i = 1;i <= n;i++){
if(a[i][0] > l && a[i][1] < r){
sum += min(a[i][0] - l,r - a[i][1]) * 1ll * 2;
}
}
return sum;
}
void test() {
cin >> k >> n;
int _i = 0;
for(int i = 1;i <= n;i++) {
char x,y;
int l,r;
cin >> x >> l >> y >> r;
if(l > r){
swap(l,r);
swap(x,y);
}
res += (r - l);
if(x == y){
continue;
}
res++;
a[++_i] = {l,r};
}
n = _i;
prec();
if(k == 1){
cout << res + solve();
return;
}
ll cur = 1e18,d = 1e18;
int j = -1;
for(int i = 0;i < (int)sc.size();i++){
cur = 1e18;
j = i - 1;
while(j + 1 < (int)sc.size()){
ll val = L[i] * 2ll + R[j + 1] * 2ll + calc(sc[i].first,sc[j + 1].first);
cur = min(cur,val);
j++;
// if(val <cur){
// j++;
// cur = val;
// }else break;
}
// cout << sc[i].first << ' ' << sc[j].first << ' ' << cur << '\n';
d = min(d,cur);
}
cout << res + d << '\n';
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
int t = 1;
// cin >> t;
while(t--) {
test();
}
}
Compilation message
bridge.cpp:8:13: error: '::main' must return 'int'
8 | #define int ll
| ^~
bridge.cpp:97:1: note: in expansion of macro 'int'
97 | int main() {
| ^~~
