Submission #1210252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210252		k1r1t0	Palembang Bridges (APIO15_bridge)	C++20	100 / 100	264 ms	11296 KiB

bridge

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 110000;
const int T = 10;
const int INF = (int)(1e18);

int n, k, p[N];
vector<pair<int, int>> seg;

int solve1() {
	if (seg.empty()) return 0;
	vector<int> tt;
	for (auto [a, b] : seg) {
		tt.push_back(a);
		tt.push_back(b);
	}
	sort(begin(tt), end(tt));
	int x = tt[n], ans = 0;
	for (auto [a, b] : seg)
		ans += abs(a - x) + abs(b - x);
	return ans;
}

struct median {
	multiset<int> l, r;
	int lsum = 0, rsum = 0;
	void rebalance() {
		auto target = (l.size() + r.size()) / 2;
		while (r.size() < target) {
			int val = *l.rbegin();
			rsum += val;
			lsum -= val;
			r.insert(val);
			l.erase(prev(l.end()));
		}
		while (target < r.size()) {
			int val = *r.begin();
			lsum += val;
			rsum -= val;
			l.insert(val);
			r.erase(r.begin());
		}
	}
	void add(int x) {
		int pr = (r.empty() ? INF : *r.begin());
		if (x <= pr) {
			l.insert(x);
			lsum += x;
		} else {
			r.insert(x);
			rsum += x;
		}
		rebalance();
	}
	void rem(int x) {
		if (l.contains(x)) {
			l.extract(x);
			lsum -= x;
		} else {
			r.extract(x);
			rsum -= x;
		}
		rebalance();
	}
	int get() {
		if (l.empty() || r.empty())
			return 0;
		return (*l.rbegin()) * l.size() - lsum + rsum - (*l.rbegin()) * r.size();
	}
};

int solve2() {
	if (seg.empty()) return 0;
	int ans = INF;
	median l, r;
	for (int t = 0; t < n; t++) {
		r.add(seg[t].first);
		r.add(seg[t].second);
	}
	for (int t = 0; t + 1 < n; t++) {
		r.rem(seg[t].first);
		r.rem(seg[t].second);
		l.add(seg[t].first);
		l.add(seg[t].second);
		ans = min(ans, l.get() + r.get());
	}
	return ans;
}

int solve() {
	if (k == 1)
		return solve1();
	return min(solve2(), solve1());
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> k >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		char p, q; int a, b; cin >> p >> a >> q >> b;
		if (a > b) swap(a, b);
		if (p == q) {
			ans += b - a;
			continue;
		} else ans++;
		seg.push_back({a, b});
	}
	n = (int) seg.size();
	sort(begin(seg), end(seg), [&](auto x, auto y) {
		return x.first + x.second < y.first + y.second;
	});
	cout << ans + solve();
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37