#include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int N=1e5+10;
int k, n;
ll ans, p[N];
vector<ll> a;
vector<pii> inf;
map<int, int> in;
bool cmp(pii a, pii b) {
return (a.f+a.s)<(b.f+b.s);
}
ll s[4];
void fix(int in, multiset<int> &a, multiset<int> &b) {
int tot=a.size()+b.size();
while(a.size()>(tot+1)/2) {
int val=*a.rbegin();
a.erase(a.find(val));
s[in]-=val;
b.insert(val);
s[in+1]+=val;
}
while(b.size()>tot/2) {
int val=*b.begin();
b.erase(b.find(val));
s[in+1]-=val;
a.insert(val);
s[in]+=val;
}
}
ll calc() {
return s[1]-s[0]+s[3]-s[2];
}
int main() {
FAST_IO;
cin >> k >> n;
FOR(i, 0, n) {
char c1, c2; int x1, x2;
cin >> c1 >> x1 >> c2 >> x2;
if(c1==c2) {
ans+=abs(x1-x2);
}
else {
inf.pb({x1,x2});
a.pb(x1);
a.pb(x2);
}
}
sort(a.begin(), a.end());
n=a.size();
ans+=n/2;
if(n==0) {
cout << ans;
return 0;
}
// if(k==1) {
// ll sm=0, cn=0;
// FORp(i, 0, n/2) sm+=a[i], cn++;
// ans+=a[n/2]*cn-sm;
//
// sm=0; cn=0;
// FOR(i, n/2+1, n) sm+=a[i], cn++;
// ans+=sm-a[n/2]*cn;
// cout << ans;
// return 0;
// }
multiset<int> l, r, le, ri;
sort(inf.begin(), inf.end(), cmp);
FOR(i, 0, inf.size()) {
le.insert(inf[i].f);
le.insert(inf[i].s);
s[2]+=inf[i].f+inf[i].s;
}
while(le.size()>(le.size()+ri.size()+1)/2) {
int val=*le.rbegin();
le.erase(le.find(val));
ri.insert(val);
s[2]-=val; s[3]+=val;
}
ll md=*ri.begin(), l_sz=le.size(), r_sz=ri.size(), now=md*l_sz-s[2]+s[3]-md*r_sz, ret=ans+now;
if(k==1) {
cout << ret;
return 0;
}
FOR(i, 0, inf.size()) {
int val=inf[i].f;
if(l.empty()) l.insert(val), s[0]+=val;
else {
int md=*l.rbegin();
if(val>=md) r.insert(val), s[1]+=val;
else l.insert(val), s[0]+=val;
}
if(le.count(val)) le.erase(le.find(val)), s[2]-=val;
else ri.erase(ri.find(val)), s[3]-=val;
val=inf[i].s;
if(l.empty()) l.insert(val), s[0]+=val;
else {
int md=*l.rbegin();
if(val>=md) r.insert(val), s[1]+=val;
else l.insert(val), s[0]+=val;
}
if(le.count(val)) le.erase(le.find(val)), s[2]-=val;
else ri.erase(ri.find(val)), s[3]-=val;
fix(0, l, r);
fix(2, le, ri);
ret=min(ret, ans+calc(l, r, le, ri));
}
cout << ret;
}
Compilation message
bridge.cpp: In function 'void fix(int, std::multiset<int>&, std::multiset<int>&)':
bridge.cpp:27:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
27 | while(a.size()>(tot+1)/2) {
| ~~~~~~~~^~~~~~~~~~
bridge.cpp:34:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
34 | while(b.size()>tot/2) {
| ~~~~~~~~^~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:3:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
| ^
bridge.cpp:82:5: note: in expansion of macro 'FOR'
82 | FOR(i, 0, inf.size()) {
| ^~~
bridge.cpp:3:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
| ^
bridge.cpp:100:5: note: in expansion of macro 'FOR'
100 | FOR(i, 0, inf.size()) {
| ^~~
bridge.cpp:126:43: error: too many arguments to function 'll calc()'
126 | ret=min(ret, ans+calc(l, r, le, ri));
| ^
bridge.cpp:43:4: note: declared here
43 | ll calc() {
| ^~~~
