Submission #521735

#	Time	Username	Problem	Language	Result	Execution time	Memory
521735		sidon	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	64 ms	8376 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define int long long

/*
K = 1:
For the bridge at i, each (x, y) incurs a cost |x-i| + |y-i|,
which can be minimized by choosing the median of these points.
K = 2:
When sorted by (x + y), it can be proved that the first bridge
is better for some prefix of pairs (x, y). Also, the median
is monotonic for increasing prefixes, so calculate for each.
*/

int K, N, ext, ans, suf[1<<17];
vector<array<int, 2>> a;

priority_queue<int> L, R; // for R: value *= -1
int l, r;

void put(int v) {
	if(empty(L) || v <= L.top())
		L.push(+v), l += v;
	else
		R.push(-v), r += v;

	if(size(L) < size(R)) {
		L.push(v = -R.top()), R.pop();
		r -= v;
		l += v;
	}
	if(size(L) > size(R) + 1) {
		R.push(v = -L.top()), L.pop();
		r -= v;
		l += v;
	}
}

int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> K >> N;

	for(int i = 0, s, t; i < N; ++i) {
		char p, q;
		cin >> p >> s >> q >> t;

		if(p == q) ext += abs(t - s);
		else {
			++ext;
			a.push_back({s, t});
		}
	}

	N = size(a);
	sort(begin(a), end(a) , [&](const auto &i, const auto &j) {
		return i[0] + i[1] < j[0] + j[1];
	});

	for(int i = N; i--; ) {
		put(a[i][0]), put(a[i][1]);
		suf[i] = r - l;
	}
	ans = suf[0];

	if(K > 1) {
		L = R = priority_queue<int> ();
		l = r = 0;

		for(int i = 0; i < N; ++i) {
			put(a[i][0]), put(a[i][1]);
			ans = min(ans, r - l + suf[i+1]);
		}
	}

	cout << ans + ext;
}

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