Submission #703744

#	Time	Username	Problem	Language	Result	Execution time	Memory
703744		600Mihnea	Palembang Bridges (APIO15_bridge)	C++17	63 / 100	2064 ms	21184 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];

struct T
{
	int fi;
	int sc;
};

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 });
	}
	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> coords;
	for (int i = 1; i <= n; i++)
	{
		coords.push_back(c1[i].second);
		coords.push_back(c2[i].second);
	}
	sort(coords.begin(), coords.end());
	vector<int> lft((int)co.size(), 0);
	vector<int> rgh((int)co.size(), 0);
	for (int i = 0; i < (int)co.size(); i++)
	{
		for (auto& s : segs)
		{
			if (s.second < co[i])
			{
				lft[i] += co[i] - s.second;
			}
		}
		for (auto& s : segs)
		{
			if (co[i] < s.first)
			{
				rgh[i] += s.first - co[i];
			}
		}
	}
	int sol = INF;
	for (int px = 0; px < (int)co.size(); px++)
	{
		vector<T> ovr;
		for (auto& s : segs)
		{
			if (co[px] <= s.first)
			{
				ovr.push_back({ s.first, s.second });
			}
		}
		sort(ovr.begin(), ovr.end(), [&](T a, T b) {return a.sc < b.sc; });
		int cnt = 0;
		for (int py = px + 1; py < (int)co.size(); py++)
		{
			int x = co[px];
			int y = co[py];
			int cur = 0;
			while (cnt < (int)ovr.size() && ovr[cnt].sc <= y)
			{
				cnt++;
			}
			for (int i = 0; i < cnt; i++)
			{
				if (x + y <= ovr[i].fi + ovr[i].sc)
				{
					cur += y - ovr[i].sc;
				}
				else
				{
					cur += ovr[i].fi - x;
				}
			}
			sol = min(sol, cur + lft[px] + rgh[py]);
		}
	}
	for (int i = 1; i <= n; i++)
	{
		extra += abs(c1[i].second - c2[i].second);
	}
	cout << 2 * 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