#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int) 1e9 + 123;
const ll LINF = (ll) 1e18 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int) (x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
bool mini(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
bool maxi(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
void run();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
run();
return 0;
}
const int N = (int) 1e5 + 123;
void operator+=(pair<ll, ll> &a, const pair<ll, ll> &b) {
a.first += b.first;
a.second += b.second;
}
struct Fenwick {
pair<ll, ll> f[2 * N];
void add(int x, pair<ll, ll> y) {
x++;
for (; x < 2 * N; x += x & (-x)) {
f[x] += y;
}
}
pair<ll, ll> get(int r) {
pair<ll, ll> res = {0, 0};
r++;
for (; r > 0; r -= r & (-r)) {
res += f[r];
}
return res;
}
void clear() {
rep(i, 0, 2 * N) f[i] = {0, 0};
}
};
int k, n;
vector<pair<ll, ll>> a;
vector<ll> cool;
ll total;
ll pref[N], suff[N];
void solve1() {
vector<ll> p;
{
for (auto &it : a) {
p.pb(it.first);
p.pb(it.second);
}
sort(all(p));
}
int k = sz(p) / 2;
ll x = p[k];
ll ans = 0;
for (ll y : p) ans += abs(x - y);
ans += total;
cout << ans << "\n";
}
int get_id(ll x) {
return (int) (lower_bound(all(cool), x) - cool.begin());
}
ll solve() {
sort(all(a), [] (const pair<ll, ll> &x, const pair<ll, ll> &y) {
return x.first + x.second < y.first + y.second;
});
Fenwick f;
{
f.clear();
multiset<ll> p, q;
ll sum = 0;
ll cnt = 0;
rep(i, 0, n) {
f.add(get_id(a[i].first), mp(a[i].first, 1));
f.add(get_id(a[i].second), mp(a[i].second, 1));
sum += a[i].first + a[i].second;
cnt += 2;
q.insert(a[i].first);
q.insert(a[i].second);
while (sz(q) > i + 1) {
ll el = *q.rbegin();
q.erase(q.find(el));
p.insert(el);
}
assert(sz(q) == sz(p));
while (*q.rbegin() > *p.begin()) {
ll x = *q.rbegin();
ll y = *p.begin();
q.erase(q.find(x));
q.insert(y);
p.erase(p.find(y));
p.insert(x);
}
ll mid = *q.rbegin();
auto it = f.get(get_id(mid));
ll sum_l = it.first;
ll sum_r = sum - sum_l;
ll cnt_l = it.second;
ll cnt_r = cnt - cnt_l;
pref[i] = (mid * cnt_l - sum_l) + (sum_r - mid * cnt_r);
}
}
{
f.clear();
multiset<ll> p, q;
ll sum = 0;
ll cnt = 0;
per(i, n - 1, 0) {
f.add(get_id(a[i].first), mp(a[i].first, 1));
f.add(get_id(a[i].second), mp(a[i].second, 1));
sum += a[i].first + a[i].second;
cnt += 2;
q.insert(a[i].first);
q.insert(a[i].second);
while (sz(q) > n - i) {
ll el = *q.rbegin();
q.erase(q.find(el));
p.insert(el);
}
assert(sz(q) == sz(p));
while (*q.rbegin() > *p.begin()) {
ll x = *q.rbegin();
ll y = *p.begin();
q.erase(q.find(x));
q.insert(y);
p.erase(p.find(y));
p.insert(x);
}
ll mid = *q.rbegin();
auto it = f.get(get_id(mid));
ll sum_l = it.first;
ll sum_r = sum - sum_l;
ll cnt_l = it.second;
ll cnt_r = cnt - cnt_l;
suff[i] = (mid * cnt_l - sum_l) + (sum_r - mid * cnt_r);
}
}
ll ans = suff[0];
rep(i, 0, n) {
mini(ans, pref[i] + suff[i + 1]);
}
return ans;
}
void run() {
cin >> k >> n;
rep(i, 0, n) {
char t1, t2;
ll x1, x2;
cin >> t1 >> x1 >> t2 >> x2;
if (t1 == t2) {
total += abs(x1 - x2);
} else {
if (x1 > x2) {
swap(t1, t2);
swap(x1, x2);
}
a.pb({x1, x2});
cool.pb(x1);
cool.pb(x2);
}
}
sort(all(cool));
cool.resize(unique(all(cool)) - cool.begin());
sort(all(a));
n = sz(a);
total += n;
if (k == 1) {
solve1();
return;
}
if (n == 0) {
cout << total << "\n";
return;
}
ll ans = solve();
ans += total;
cout << ans << "\n";
}
Compilation message
Compilation timeout while compiling bridge
