Submission #1294884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294884		arashmemar	Road Construction (JOI21_road_construction)	C++20	0 / 100	10085 ms	26976 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;

const long long int maxn = 3e5;

pair <long long int, long long int> a[maxn];

pair <long long int, int> b[maxn];

set <pair <long long int, long long int>> s;

int p[maxn];

vector <long long int> ans1, ans2;

bool is_ar(int i, int j)
{
	return a[j].first >= a[i].first and a[j].second >= a[i].second;
}

bool is_br(int i, int j)
{
	return a[j].first > a[i].first and a[j].second < a[i].second;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long int n, k;
	cin >> n >> k;
	for (long long int i = 1;i <= n;i++)
	{
		cin >> a[i].first >> a[i].second;
	}

	b[n + 1] = {2e14, n + 1};
	a[n + 1] = {1e9 + 10, 1e9 + 10};

	for (long long int i = 1;i <= n;i++)
	{
		b[i] = {a[i].first + a[i].second, i};
	}
	sort(b + 1, b + 1 + n);
	for (int i = 1;i <= n;i++)
	{
		p[i] = i + 1;
		while (!is_ar(b[i].second, b[p[i]].second))
		{
			p[i]++;
		}
		s.insert({b[p[i]].first - b[i].first, i});
	}

	int q = k;
	while (q-- and (*s.begin()).first <= 1e12)
	{
		ans1.push_back((*s.begin()).first);
		int i = (*s.begin()).second;
		s.erase(s.begin());
		p[i]++;
		while (!is_ar(b[i].second, b[p[i]].second))
		{
			p[i]++;
		}
		s.insert({b[p[i]].first - b[i].first, i});
	}

	s.clear();

	a[n + 1] = {1e9 + 10, -1e9 - 10};

	for (long long int i = 1;i <= n;i++)
	{
		b[i] = {a[i].first - a[i].second, i};
	}
	sort(b + 1, b + 1 + n);
	for (long long int i = 1;i <= n;i++)
	{
		p[i] = i + 1;
		while (!is_br(b[i].second, b[p[i]].second))
		{
			p[i]++;
		}
		s.insert({b[p[i]].first - b[i].first, i});
	}

	q = 0;
	while (q-- and (*s.begin()).first <= 1e13)
	{
		ans2.push_back((*s.begin()).first);
		int i = (*s.begin()).second;
		s.erase(s.begin());
		p[i]++;
		while (!is_br(b[i].second, b[p[i]].second))
		{
			p[i]++;
		}
		s.insert({b[p[i]].first - b[i].first, i});
	}

	ans1.push_back(1e13);
	ans2.push_back(1e13);

	int pt1 = 0, pt2 = 0;
	for (int i = 1;i <= k;i++)
	{
		if (ans1[pt1] < ans2[pt2])
		{
			cout << ans1[pt1++] << '\n';
		}
		else
		{
			cout << ans2[pt2++] << '\n';
		}
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35