Submission #705549

#	Time	Username	Problem	Language	Result	Execution time	Memory
705549		600Mihnea	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2071 ms	10076 KiB

bridge

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

#define int long long 

const int INF = (int)1e18 + 7;

pair<int, int> _rd_()
{
	string s;
	int i;
	cin >> s >> i;
	assert(s == "A" || s == "B");
	return { s == "B", i };
}

const int N = (int)1e5 + 7;
int k;
int n;
int extra;
pair<int, int> c1[N], c2[N];


signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	cin >> k >> n;
	{
		int y = 0;
		for (int i = 1; i <= n; i++)
		{
			c1[i] = _rd_();
			c2[i] = _rd_();
			if (c1[i].first == c2[i].first)
			{
				extra += abs(c1[i].second - c2[i].second);
				continue;
			}
			y++;
			c1[y] = c1[i];
			c2[y] = c2[i];
		}
		n = y;
	}
	if (n == 0)
	{
		cout << extra << "\n";
		return 0;
	}
	if (k == 1)
	{
		vector<int> coords;
		for (int i = 1; i <= n; i++)
		{
			coords.push_back(c1[i].second);
			coords.push_back(c2[i].second);
		}
		nth_element(coords.begin(), coords.begin() + n - 1, coords.end());
		int su = 0;
		for (int i = 0; i < 2 * n; i++)
		{
			su += abs(coords[i] - coords[n - 1]);
		}
		cout << su + extra + n << "\n";
		return 0;
	}
	assert(k == 2);
	set<int> s;
	for (int i = 1; i <= n; i++)
	{
		s.insert(c1[i].second);
		s.insert(c2[i].second);
		if (c1[i].second > c2[i].second)
		{
			swap(c1[i], c2[i]);
		}
	}
	vector<pair<int, int>> segs;
	for (int i = 1; i <= n; i++)
	{
		segs.push_back({ c1[i].second, c2[i].second });
		if (!(segs.back().first <= segs.back().second))
		{
			swap(segs.back().first, segs.back().second);
		}
		assert(segs.back().first <= segs.back().second);
	}
	sort(segs.begin(), segs.end(), [&](pair<int, int> a, pair<int, int> b) {return a.first + a.second < b.first + b.second; });
	vector<int> co;
	for (auto& x : s)
	{
		co.push_back(x);
	}
	assert(!co.empty());
	co.push_back(co.back());
	assert((int)co.size() >= 2);
	vector<int> values;
	for (int i = 0; i < (int)segs.size(); i++)
	{
		values.push_back(segs[i].first);
		values.push_back(segs[i].second);
	}
	vector<int> what((int)values.size() + 1, 0);
	multiset<int> low, high;
	auto clr = [&]()
	{
		low.clear();
		high.clear();
	};
	auto baga = [&](int x)
	{
		if (low.empty())
		{
			high.insert(x);
		}
		else
		{
			if (high.empty())
			{
				low.insert(x);
			}
			else
			{
				assert(!low.empty());
				assert(!high.empty());
				if (x >= *high.begin())
				{
					high.insert(x);
				}
				else
				{
					low.insert(x);
				}
			}
		}
		while ((int)high.size() - 1 >= (int)low.size() + 1)
		{
			assert(!high.empty());
			low.insert(*high.begin());
			high.erase(high.begin());
		}
		while ((int)low.size() - 1 >= (int)high.size() + 1)
		{
			assert(!low.empty());
			auto it = low.end();
			it--;
			high.insert(*it);
			low.erase(it);
		}
		assert(abs((int)low.size() - (int)high.size()) <= 1);
	};
	auto get = [&]()
	{
		assert(!low.empty());
		assert(!high.empty());
		assert((int)low.size() == (int)high.size());
		int sol = 0, val = *high.begin();
		for (auto& it : low)
		{
			sol += abs(it - val);
		}
		for (auto& it : high)
		{
			sol += abs(it - val);
		}
		return sol;
	};
	clr();
	int sol = INF;
	for (int from = 0; from <= (int)values.size(); from += 2)
	{
		if (from >= 2)
		{
			baga(values[from - 2]);
			baga(values[from - 1]);
			what[from] += get();
		}
	}
	clr();
	for (int from = (int)values.size(); from >= 0; from -= 2)
	{
		if (from < (int)values.size())
		{
			baga(values[from]);
			baga(values[from + 1]);
			what[from] += get();
		}
		sol = min(sol, what[from]);
	}
	cout << sol + extra + n << "\n";
	return 0;
}

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