#include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <cstdlib> using namespace std; struct path { long long a; long long b; }; bool operator < (path X, path Y) { return X.a + X.b < Y.a + Y.b; }; multiset<long long> left_low, left_high, right_low, right_high; long long left_low_sum = 0, left_high_sum = 0, right_low_sum = 0, right_high_sum = 0; void rebalance() { for(int rep = 1; rep <= 2; rep++) { if(right_high.size() > right_low.size() || (!right_low.empty() && !right_high.empty() && *right_low.rbegin() > *right_high.begin())) { long long x = *right_high.begin(); right_high.erase(right_high.begin()); right_high_sum -= x; right_low.insert(x); right_low_sum += x; } if(right_low.size() > right_high.size() || (!right_low.empty() && !right_high.empty() && *right_low.rbegin() > *right_high.begin())) { long long x = *right_low.rbegin(); right_low.erase(right_low.find(x)); right_low_sum -= x; right_high.insert(x); right_high_sum += x; } if(left_high.size() > left_low.size() || (!left_low.empty() && !left_high.empty() && *left_low.rbegin() > *left_high.begin())) { long long x = *left_high.begin(); left_high.erase(left_high.begin()); left_high_sum -= x; left_low.insert(x); left_low_sum += x; } if(left_low.size() > left_high.size() || (!left_low.empty() && !left_high.empty() && *left_low.rbegin() > *left_high.begin())) { long long x = *left_low.rbegin(); left_low.erase(left_low.find(x)); left_low_sum -= x; left_high.insert(x); left_high_sum += x; } } } int main() { int K, N; cin >> K >> N; if(K == 1) { long long res = 0; char c1, c2; long long e1, e2; vector<long long> A; for(int i = 1; i <= N; i++) { cin >> c1 >> e1 >> c2 >> e2; if(c1 == c2) res += abs(e1 - e2); else { A.push_back(e1); A.push_back(e2); res += 1; } } sort(A.begin(), A.end()); for(int i = 0; i < A.size(); i++) res += abs(A[i] - A[A.size()/2]); cout << res << '\n'; return 0; } else { long long res = 0; vector<path> P; long long basic = 0; for(int i = 1; i <= N; i++) { char c1, c2; int e1, e2; cin >> c1 >> e1 >> c2 >> e2; if(c1 == c2) { basic += abs(e1 - e2); } else { basic++; if(e1 > e2) swap(e1, e2); P.push_back(path{e1, e2}); } } sort(P.begin(), P.end()); // for(path p:P) cerr << p.a << ' ' << p.b << '\n'; // cerr << "\n\n\n"; //initially, everything is in right for(path p:P) { right_high.insert(p.a); right_high_sum += p.a; right_high.insert(p.b); right_high_sum += p.b; } rebalance(); // for(int x: right_low) cerr << x << ' '; // cerr << '\n'; // for(int x: right_high) cerr << x << ' '; // cerr << '\n'; res = right_high_sum - right_low_sum; // for(int uv: left_low) cerr << uv << ' '; // cerr << '\n'; // for(int uv: left_high) cerr << uv << ' '; // cerr << '\n'; // for(int uv: right_low) cerr << uv << ' '; // cerr << '\n'; // for(int uv: right_high) cerr << uv << ' '; // cerr << '\n'; // // cerr << "\n\n\n"; // // cerr << res << '\n'; for(path p:P) { for(long long val: {p.a, p.b}) { if(right_high.find(val) != right_high.end()) { right_high.erase(val); right_high_sum -= val; } else { right_low.erase(val); right_low_sum -= val; } } left_high.insert(p.a); left_high_sum += p.a; left_high.insert(p.b); left_high_sum += p.b; // for(int uv: left_low) cerr << uv << ' '; // cerr << '\n'; // for(int uv: left_high) cerr << uv << ' '; // cerr << '\n'; // for(int uv: right_low) cerr << uv << ' '; // cerr << '\n'; // for(int uv: right_high) cerr << uv << ' '; // cerr << '\n'; // cerr << "sum = " << left_high_sum - left_low_sum << ' ' << right_high_sum - right_low_sum << '\n'; // // cerr << "\n\n\n"; rebalance(); res = min(res, left_high_sum - left_low_sum + right_high_sum - right_low_sum); } res += basic; cout << res << '\n'; } }

bridge.cpp: In function 'int main()':
bridge.cpp:102:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int i = 0; i < A.size(); i++) res += abs(A[i] - A[A.size()/2]);
      |                        ~~^~~~~~~~~~