Submission #1043015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043015		Aldas25	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	60 ms	8104 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 100;
const ll INF = 1e13;

vector<pair<ll, ll>> a;
priority_queue<ll> lowerHalf;
priority_queue<ll, vector<ll>, greater<ll>> upperHalf;
ll lowerSum, upperSum;

void ins(ll x) {
	if (lowerHalf.empty() || x <= lowerHalf.top()) {
		lowerHalf.push(x);
		lowerSum += x;
	}
	else {
		upperHalf.push(x);
		upperSum += x;
	}

	if (upperHalf.size() + 1 < lowerHalf.size()) {
		ll y = lowerHalf.top();
		lowerHalf.pop();
		upperHalf.push(y);
		lowerSum -= y;
		upperSum += y;
	} else if (lowerHalf.size() < upperHalf.size()) {
		ll y = upperHalf.top();
		upperHalf.pop();
		lowerHalf.push(y);
		upperSum -= y;
		lowerSum += y;
	}
}

ll getSumOfDistances() {
	return upperSum - lowerSum; // works since there are always an even number of elements in priority queues combined
}

ll pref[MAXN];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);

	ll sumInSameSide = 0;

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

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

	if (a.size() == 0) {
		cout << sumInSameSide << "\n";
		return 0;
	}

	sort(a.begin(), a.end(), [](pair<ll, ll> f, pair<ll, ll> s) {
		return (f.first + f.second) < (s.first + s.second);
	});
	
	for (int i = 0; i < a.size(); i++) {
		auto p = a[i];
		ins(p.first);
		ins(p.second);

		pref[i] = getSumOfDistances();
	}

	ll ans = pref[a.size()-1];

	if (k == 2) {
		while (lowerHalf.size()) {lowerHalf.pop();}
		while (upperHalf.size()) {upperHalf.pop();}
		lowerSum = upperSum = 0;

		for (int i = a.size() - 1; i >= 0; i--) {
			auto p = a[i];
			ins(p.first);
			ins(p.second);

			ll curVal = getSumOfDistances() + (i > 0 ? pref[i-1] : 0);
			ans = min(ans, curVal);
		}
	}

	cout << sumInSameSide + ans + a.size() << "\n";

	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~

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