#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const ll inf = 1e18; vector<pair<int, int> > eve; vector<ll> places; ll Answer = inf; vector<ll> seg[4 * maxn], par[4 * maxn]; void build(int id, int L, int R){ if (L + 1 == R){ seg[id].push_back(eve[L].first); seg[id].push_back(eve[L].second); sort(seg[id].begin(), seg[id].end()); par[id].push_back(seg[id][0]); par[id].push_back(seg[id][0] + seg[id][1]); return; } int mid = (L + R) >> 1; build(2 * id + 0, L, mid); build(2 * id + 1, mid, R); for (int i = 0; i < seg[2 * id + 0].size(); i++) seg[id].push_back(seg[2 * id + 0][i]); for (int i = 0; i < seg[2 * id + 1].size(); i++) seg[id].push_back(seg[2 * id + 1][i]); sort(seg[id].begin(), seg[id].end()); par[id].push_back(seg[id][0]); for (int i = 1; i < seg[id].size(); i++) par[id].push_back(par[id].back() + seg[id][i]); } ll get(int id, int L, int R, int l, int r, int x){ if (L == l and R == r){ // cout << "Get : " << L << " " << R << " " << x << endl; // for (auto it : seg[id]) // cout << it << " "; // cout << endl; int idx = upper_bound(seg[id].begin(), seg[id].end(), x) - seg[id].begin() - 1; // cout << idx << " -> " << endl; if (idx < 0) return par[id].back() - 1ll * seg[id].size() * x; if (idx == seg[id].size() - 1) return 1ll * seg[id].size() * x - par[id].back(); ll pre = 1ll * x * (idx + 1) - par[id][idx]; ll suf = (par[id].back() - par[id][idx]) - 1ll * (seg[id].size() - idx - 1) * x; // cout << pre << " " << suf << endl; return pre + suf; } ll sum = 0; int mid = (L + R) >> 1; if (l < mid) sum += get(2 * id + 0, L, mid, l, min(mid, r), x); if (mid < r) sum += get(2 * id + 1, mid, R, max(l, mid), r, x); return sum; } bool cmp(pair<int,int> fi, pair<int, int> se){ return fi.first + fi.second < se.first + se.second; } ll calculate(int i, int j){ int k = (places[i] + places[j]); int lo = -1, hi = eve.size(); while (hi - lo > 1){ int mid = (lo + hi) >> 1; if (eve[mid].first + eve[mid].second <= k) lo = mid; else hi = mid; } int q = eve.size(); ll sum = 0; if (hi > 0) sum += get(1, 0, q, 0, hi, places[i]); if (hi != q) sum += get(1, 0, q, hi, q, places[j]); // cout << places[i] << " " << places[j] << " lo is : " << lo << " -> " << sum << endl; return sum; } void find(int L, int R, int l, int r){ if (L >= R) return; int mid = (L + R) >> 1; ll k = inf, idx = -1; for (int i = l; i < min(mid, r); i++){ ll tmp = calculate(i, mid); if (tmp < k){ k = tmp; idx = i; } } Answer = min(Answer, k); find(L, mid, l, idx + 1); find(mid + 1, R, idx, r); } ll solve(){ int n = eve.size(); vector<ll> a(2 * n + 1); for (int i = 0; i < n; i++){ a[2 * i + 0 + 1] = eve[i].first; a[2 * i + 1 + 1] = eve[i].second; } sort(a.begin() + 1, a.end()); n = 2 * n; for (int i = 1; i <= n; i++) a[i] += a[i - 1]; ll answer = inf; for (int i = 1; i <= n; i++){ ll T = a[i] - a[i - 1]; answer = min(answer, T * (i - (n - i)) - a[i] + (a[n] - a[i])); } return answer + eve.size(); } int main(){ ios_base::sync_with_stdio(false); int k, n; cin >> k >> n; ll answer = 0; for (int i = 0; i < n; i++){ int x, y; char a, b; cin >> a >> x >> b >> y; if (a == b){ answer += abs(x - y); continue; } if (a == 'B') swap(x, y); eve.push_back({x, y}); } if (eve.empty()) return cout << answer << endl, 0; if (k == 1){ cout << answer + solve() << '\n'; return 0; } for (int i = 0; i < eve.size(); i++){ places.push_back(eve[i].first); places.push_back(eve[i].second); } sort(places.begin(), places.end()); int m = places.size(); int q = eve.size(); sort(eve.begin(), eve.end(), cmp); build(1, 0, q); find(0, m, 0, m); cout << Answer + answer + eve.size() << endl; return 0; }

bridge.cpp: In function 'void build(int, int, int)':
bridge.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < seg[2 * id + 0].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < seg[2 * id + 1].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < seg[id].size(); i++)
                  ~~^~~~~~~~~~~~~~~~
bridge.cpp: In function 'll get(int, int, int, int, int, int)':
bridge.cpp:46:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (idx == seg[id].size() - 1)
       ~~~~^~~~~~~~~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:145:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < eve.size(); i++){
                  ~~^~~~~~~~~~~~