#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define db double #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second #define pb push_back #define all(x) begin(x), end(x) #define allr(x) rbegin(x), rend(x) #define szx(x) ((int)(x).size()) #define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i) #define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; --i) #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) #define endl '\n' #define inf 1000000007 #define mod 1000000007 // #define mod 998244353 using namespace std; using namespace __gnu_pbds; void setIO() { ios::sync_with_stdio(0); cin.tie(0); } void openFile(string filename = "") { if (!filename.empty()) if (ifstream(filename + ".in")) { freopen((filename + ".in").c_str(), "r", stdin); freopen((filename + ".out").c_str(), "w", stdout); } } const int MAX = 1e5 + 5; int n, k; vector<pii> a; vector<int> compress{-1}; ll s1 = 0; struct SegmentTree { vector<pair<int, ll>> st; int _n; SegmentTree(int _n) { n = _n; st.resize(4 * n); } void update(pii x, int s = 1) { update(x.fi, s, s * compress[x.fi]); update(x.se, s, s * compress[x.se]); } void update(int x, int y, ll z, int id = 1, int l = 1, int r = n) { if (l == r) { st[id].fi += y; st[id].se += z; return; } int mid = (l + r) >> 1; if (x <= mid) update(x, y, z, 2 * id, l, mid); else update(x, y, z, 2 * id + 1, mid + 1, r); st[id].fi = st[2 * id].fi + st[2 * id + 1].fi; st[id].se = st[2 * id].se + st[2 * id + 1].se; } int med(int id = 1, int l = 1, int r = n, int acc = 0) { if (l == r) return l; int mid = (l + r) >> 1; if (acc + st[2 * id].fi > getmid()) return med(2 * id, l, mid, acc); else return med(2 * id + 1, mid + 1, r, acc + st[2 * id].fi); } pair<int, ll> query(int u, int v = n, int id = 1, int l = 1, int r = n) { if (u > v) return {0, 0}; if (r < u || l > v) return {0, 0}; if (l >= u && r <= v) return st[id]; int mid = (l + r) >> 1; pair<int, ll> q1 = query(u, v, 2 * id, l, mid); pair<int, ll> q2 = query(u, v, 2 * id + 1, mid + 1, r); return {q1.fi + q2.fi, q1.se + q2.se}; } int getmid() { return (st[1].fi + 1) / 2; } ll getans() { int m = med(); pair<int, ll> q1 = query(1, m - 1), q2 = query(m + 1); return q2.se - q1.se - 1LL * (q2.fi - q1.fi) * compress[m]; } }; void solve() { int m = szx(a); s1 += m; REP(i, m) compress.pb(a[i].fi), compress.pb(a[i].se); sort(all(compress)); compress.erase(unique(all(compress)), compress.end()); SegmentTree pref(szx(compress)), suff(szx(compress)); REP(i, m) { a[i].fi = lower_bound(all(compress), a[i].fi) - compress.begin(); a[i].se = lower_bound(all(compress), a[i].se) - compress.begin(); suff.update(a[i]); } REP(i, m) suff.update(a[i], -1); ll mn = 1e18; if (k == 1) { mn = suff.getans(); } else { sort(all(a), [&](pii x, pii y) { return compress[x.fi] + compress[x.se] < compress[y.fi] + compress[y.se]; }); REP(i, m) { mn = min(mn, pref.getans() + suff.getans()); suff.update(a[i], -1); pref.update(a[i]); } } cout << s1 + mn; } void input() { cin >> k >> n; REP(i, n) { char A, B; int s, t; cin >> A >> s >> B >> t; if (A != B) a.pb({s, t}); else s1 += abs(s - t); } } void preprocess() {} void reset() {} int main() { setIO(); openFile("main"); int t = 1; // cin >> t; preprocess(); while (t--) { reset(); input(); solve(); } }

bridge.cpp: In function 'void openFile(std::string)':
bridge.cpp:32:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |             freopen((filename + ".in").c_str(), "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:33:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |             freopen((filename + ".out").c_str(), "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~