Submission #1115679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115679		staszic_ojuz	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	136 ms	20040 KiB

ho_t1

// Patryk Niemczyk jln.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

long long czytaj(vector<long long> &drzewo, long long v, long long vl, long long vp, long long a, long long b)
{
	if (b < a)
		return 0;
	if (vl >= a && vp <= b)
		return drzewo[v];
	else if (vl > b || vp < a)
		return 0;
	else
	{
		long long mid = (vl + vp) / 2;
		return max(czytaj(drzewo, v * 2, vl, mid, a, b), czytaj(drzewo, v * 2 + 1, mid + 1, vp, a, b));
	}
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	long long n;
	cin >> n;

	vector<pair<long long, long long>> pierwsze(n + 1);
	vector<long long> drugie(n);

	for (long long i = 0; i <= n; ++i)
	{
		cin >> pierwsze[i].first;
		pierwsze[i].second = i;
	}
	for (long long i = 0; i < n; ++i)
		cin >> drugie[i];

	sort(pierwsze.begin(), pierwsze.end());
	sort(drugie.begin(), drugie.end());

	// for (long long i = 0; i <= n; ++i)
	// 	cout << pierwsze[i].first << " ";
	// cout << '\n';
	// for (long long i = 0; i < n; ++i)
	// 	cout << drugie[i] << " ";
	// cout << '\n';

	long long rozmiar = pow(2, ceil(log2(n)));

	vector<long long> roz1(2 * rozmiar, 0);
	vector<long long> roz2(2 * rozmiar, 0);

	for (long long i = rozmiar; i - rozmiar < n; ++i)
	{
		roz1[i] = pierwsze[i - rozmiar].first - drugie[i - rozmiar];
		roz2[i] = pierwsze[i - rozmiar + 1].first - drugie[i - rozmiar];
	}

	for (long long i = rozmiar - 1; i > 0; --i)
	{
		roz1[i] = max(roz1[2 * i], roz1[2 * i + 1]);
		roz2[i] = max(roz2[2 * i], roz2[2 * i + 1]);
	}

	// for (long long i = 1; i < roz1.size(); ++i)
	// {
	// 	if (i == pow(2, ceil(log2(i))))
	// 		cout << '\n';
	// 	cout << roz1[i] << " ";
	// }
	// cout << '\n';
	// for (long long i = 1; i < roz2.size(); ++i)
	// {
	// 	if (i == pow(2, ceil(log2(i))))
	// 		cout << '\n';
	// 	cout << roz2[i] << " ";
	// }
	// cout << '\n';

	vector<long long> odp(n + 1);

	for (long long i = 0; i <= n; ++i)
	{
		// cout << "Max 1 na przedziale: 1 - " << i << ": " << czytaj(roz1, 1, 1, rozmiar, 1, i) << '\n';
		// cout << "Max 2 na przedziale: " << i + 1 << " - " << rozmiar << ": " << czytaj(roz2, 1, 1, rozmiar, i + 1, rozmiar) << '\n';
		odp[pierwsze[i].second] = max(czytaj(roz1, 1, 1, rozmiar, 1, i), czytaj(roz2, 1, 1, rozmiar, i + 1, rozmiar));
	}

	for (long long o : odp)
		cout << o << " ";
	cout << '\n';

	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91