Submission #260940

#	Time	Username	Problem	Language	Result	Execution time	Memory
260940		atoiz	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	512 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <cassert>

using namespace std;

struct Balancer
{
	multiset<int> lef, rig;
	int cntLef, cntRig;
	int64_t sumLef, sumRig;

	Balancer()
	{
		lef.clear(), rig.clear();
		cntLef = 0, cntRig = 0;
		sumLef = 0, sumRig = 0;
	}

	void add(int l, int r)
	{
		// cout << "add " << l << ' ' << r << endl;
		l = l << 1, r = r << 1 | 1;
		int mid = (!lef.empty() ? *lef.rbegin() : 0);

		if (l <= mid) lef.insert(l);
		else rig.insert(l), sumRig += l / 2, ++cntRig;

		if (r <= mid) lef.insert(r), sumLef += r / 2, ++cntLef;
		else rig.insert(r);

		while (((int) rig.size()) - ((int) lef.size()) > 1) {
			int x = *rig.begin();
			rig.erase(rig.begin());
			lef.insert(lef.end(), x);
			if (x & 1) sumLef += x / 2, ++cntLef;
			else sumRig -= x / 2, --cntRig;
		}

		while (((int) lef.size()) - ((int) rig.size()) > 1) {
			int x = *lef.rbegin();
			lef.erase(prev(lef.end()));
			rig.insert(rig.begin(), x);
			if (x & 1) sumLef -= x / 2, --cntLef;
			else sumRig += x / 2, ++cntRig;
		}
	}

	int64_t get()
	{
		if (lef.empty() && rig.empty()) return 0;
		int64_t mid = (lef.empty() ? *rig.begin() : *lef.rbegin());
		// cout << "get " << (cntLef - cntRig) * mid - sumLef + sumRig << endl;
		return (cntLef - cntRig) * mid - sumLef + sumRig;
	}
};

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int K, M;
	cin >> K >> M;
	vector<pair<int, int>> vec;
	int64_t offset = 0;
	while (M--) {
		char cA, cB;
		int valA, valB;
		cin >> cA >> valA >> cB >> valB;
		if (valA > valB) swap(valA, valB);
		offset += valB - valA;
		if (cA != cB) vec.emplace_back(valA, valB);
	}

	M = (int) vec.size();
	offset += M;
	sort(vec.begin(), vec.end(), [&](pair<int, int> p, pair<int, int> q) { return p.first + p.second < q.first + q.second; });

	vector<int64_t> pref(M, 0);
	Balancer bal;
	for (int i = 0; i < M; ++i) {
		bal.add(vec[i].first, vec[i].second);
		pref[i] = bal.get();
	}

	int64_t ans = pref[M - 1];
	if (K == 1) return cout << offset + 2 * ans << endl, 0;

	bal = Balancer();
	for (int i = M - 1; i > 0; --i) {
		bal.add(vec[i].first, vec[i].second);
		ans = min(ans, bal.get() + pref[i - 1]);
	}
	cout << offset + 2 * ans << endl;
}

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