Submission #831777

#	Time	Username	Problem	Language	Result	Execution time	Memory
831777		serifefedartar	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2072 ms	12028 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 18
#define MAXN 200005

vector<pair<ll,ll>> seq;
int main() {
	fast
	ll K, N;
	cin >> K >> N;

	ll sum = 0;
	for (int i = 0; i < N; i++) {
		char ch1, ch2;
		ll posR1, posR2;
		cin >> ch1 >> posR1 >> ch2 >> posR2;

		if (ch1 == ch2)
			sum += abs(posR1 - posR2);
		else
			seq.push_back({min(posR1, posR2), max(posR1, posR2)});
	}
	sort(seq.begin(), seq.end(), [&](pair<int,int> a, pair<int,int> b) {
		return a.f + a.s < b.f + b.s;
	});
	sum += seq.size();

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

	multiset<int> sR1, sR2, sL1, sL2;
	ll sumR1 = 0, sumR2 = 0, sumL1 = 0, sumL2 = 0;
	for (int i = 0; i < (ll)seq.size()/2; i++) {
		sR1.insert(seq[i].f);
		sR1.insert(seq[i].s);
		sumR1 += seq[i].f + seq[i].s;
	}
	for (int i = (ll)seq.size()/2; i < ((ll)seq.size()/2) * 2; i++) {
		sR2.insert(seq[i].f);
		sR2.insert(seq[i].s);
		sumR2 += seq[i].f + seq[i].s;
	}
	if (seq.size() % 2) {
		sR1.insert(seq[seq.size()-1].f);
		sR2.insert(seq[seq.size()-1].s);
		sumR1 += seq[seq.size()-1].f;
		sumR2 += seq[seq.size()-1].s;
	}

	while (*(--sR1.end()) > *(sR2.begin())) {
		sR1.insert(*(sR2.begin()));
		sumR1 += *(sR2.begin());
		sumR2 -= *(sR2.begin());
		sR2.erase(sR2.begin());
		sR2.insert(*(--sR1.end()));
		sumR2 += *(--sR1.end());
		sumR1 -= *(--sR1.end());
		sR1.erase(sR1.find(*(--sR1.end())));
	}

	ll median = *(--sR1.end());
	ll ans = (ll)sR1.size()*median - sumR1 + sumR2 - (ll)sR2.size()*median + sum;
	if (K == 2) {
		for (int i = 0; i < (ll)seq.size() - 1; i++) {
			ll val1 = seq[i].f;
			ll val2 = seq[i].s;
			if (sR1.count(val1)) {
				sR1.erase(sR1.find(val1));
				sumR1 -= val1;
			} else {
				sR2.erase(sR2.find(val1));
				sumR2 -= val1;
			}
			if (sR1.count(val2)) {
				sR1.erase(sR1.find(val2));
				sumR1 -= val2;
			} else {
				sR2.erase(sR2.find(val2));
				sumR2 -= val2;
			}
			sL1.insert(val1);
			sL2.insert(val2);
			sumL1 += val1;
			sumL2 += val2;

			while (sR1.size() > sR2.size()) {
				sR2.insert(*(--sR1.end()));
				sumR2 += *(--sR1.end());
				sumR1 += *(--sR1.end());
				sR1.erase(sR1.find(*(--sR1.end())));
			}
			while (sR2.size() > sR1.size()) {
				sR1.insert(*(sR2.begin()));
				sumR1 += *(sR2.begin());
				sumR2 -= *(sR2.begin());
				sR2.erase(sR2.begin());
			}
			while (sL1.size() > sL2.size()) {
				sL2.insert(*(--sL1.end()));
				sumL2 += *(--sL1.end());
				sumL1 += *(--sL1.end());
				sL1.erase(sL1.find(*(--sL1.end())));
			}
			while (sL2.size() > sL1.size()) {
				sL1.insert(*(sL2.begin()));
				sumL1 += *(sL2.begin());
				sumL2 -= *(sL2.begin());
				sL2.erase(sL2.begin());
			}
			while (*(--sR1.end()) > *(sR2.begin())) {
				sR1.insert(*(sR2.begin()));
				sumR1 += *(sR2.begin());
				sumR2 -= *(sR2.begin());
				sR2.erase(sR2.begin());
				sR2.insert(*(--sR1.end()));
				sumR2 += *(--sR1.end());
				sumR1 -= *(--sR1.end());
				sR1.erase(sR1.find(*(--sR1.end())));
			}
			while (*(--sL1.end()) > *(sL2.begin())) {
				sL1.insert(*(sL2.begin()));
				sumL1 += *(sL2.begin());
				sumL2 -= *(sL2.begin());
				sL2.erase(sL2.begin());
				sL2.insert(*(--sL1.end()));
				sumL2 += *(--sL1.end());
				sumL1 -= *(--sL1.end());
				sL1.erase(sL1.find(*(--sL1.end())));
			}

			ll median1 = *(--sR1.end());
			ll median2 = *(--sL1.end());
			ans = min(ans, (ll)sR1.size()*median1 - sumR1 + sumR2 - (ll)sR2.size()*median1 + sum
						+ (ll)sL1.size()*median2 - sumL1 + sumL2 - (ll)sL2.size()*median2);
		}
	}

	cout << ans << "\n";
}

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