Submission #1045168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045168		sssamui	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	181 ms	14324 KiB

bridge

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
using LL = long long;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int k, n;
	cin >> k >> n;
	LL fans = 0;
	vector<pair<LL, pair<LL, LL>>> inv(0);
	vector<LL> invnums(0);
	while (n--)
	{
		char a, c;
		LL b, d;
		cin >> a >> b >> c >> d;
		if (a == c)
		{
			if (b > d) fans += b - d;
			else fans += d - b;
		}

		else
		{
			fans++;
			invnums.push_back(b), invnums.push_back(d);
			inv.push_back({ b + d, {b, d} });
		}
	}

	n = inv.size();
	sort(invnums.begin(), invnums.end()), sort(inv.begin(), inv.end());
	LL llsum = 0, lrsum = 0, rlsum = 0, rrsum = 0, lmid = -1, rmid = -1;
	multiset<LL> ll, lr, rl, rr;
	for (int i = 0; i < n; i++)
	{
		rl.insert(-invnums[i]);
		rlsum += invnums[i];
	}

	for (int i = n; i < 2 * n; i++)
	{
		rr.insert(invnums[i]);
		rrsum += invnums[i];
	}

	rmid = -*rl.begin();
	LL ans = rrsum - rlsum;
	if (k == 2) for (int i = 0; i < n - 1; i++)
	{
		if (inv[i].second.first > rmid)
		{
			rrsum -= inv[i].second.first;
			rr.erase(rr.find(inv[i].second.first));
			if (inv[i].second.second <= rmid)
			{
				rlsum -= inv[i].second.second;
				rl.erase(rl.find(-inv[i].second.second));
				rmid = -*rl.begin();
			}

			else
			{
				rrsum -= inv[i].second.second;
				rr.erase(rr.find(inv[i].second.second));
				rrsum += rmid;
				rr.insert(rmid);
				rlsum -= rmid;
				rl.erase(rl.begin());
				rmid = -*rl.begin();
			}
		}

		else
		{
			rlsum -= inv[i].second.first;
			rl.erase(rl.find(-inv[i].second.first));
			rmid = -*rl.begin();
			if (inv[i].second.second > rmid)
			{
				rrsum -= inv[i].second.second;
				rr.erase(rr.find(inv[i].second.second));
			}

			else
			{
				rlsum -= inv[i].second.second;
				rl.erase(rl.find(-inv[i].second.second));
				rmid = *rr.begin();
				rlsum += rmid;
				rl.insert(-rmid);
				rrsum -= rmid;
				rr.erase(rr.begin());
			}
		}

		if (inv[i].second.first > lmid)
		{
			lr.insert(inv[i].second.first);
			lrsum += inv[i].second.first;
			if (inv[i].second.second <= lmid)
			{
				ll.insert(-inv[i].second.second);
				llsum += inv[i].second.second;
				lmid = -*ll.begin();
			}

			else
			{
				lr.insert(inv[i].second.second);
				lrsum += inv[i].second.second;
				lmid = *lr.begin();
				lrsum -= lmid;
				lr.erase(lr.begin());
				ll.insert(-lmid);
				llsum += lmid;
			}
		}

		else
		{
			ll.insert(-inv[i].second.first);
			llsum += inv[i].second.first;
			if (inv[i].second.second >= lmid)
			{
				lrsum += inv[i].second.second;
				lr.insert(inv[i].second.second);
			}

			else
			{
				llsum += inv[i].second.second;
				ll.insert(-inv[i].second.second);
				lrsum += lmid;
				lr.insert(lmid);
				llsum -= lmid;
				ll.erase(ll.begin());
				lmid = -*ll.begin();
			}
		}

		ans = fmin(ans, (rrsum - rlsum) + (lrsum - llsum));
	}

	fans += ans;
	cout << fans;
}

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