結果

問題 No.3325 陰陽師
コンテスト
ユーザー elphe
提出日時 2025-09-28 19:05:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 113 ms / 2,000 ms
コード長 8,342 bytes
コンパイル時間 3,457 ms
コンパイル使用メモリ 288,944 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-11-01 02:53:37
合計ジャッジ時間 6,967 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
In member function ‘constexpr uint_fast32_t MyLib::MaxSegmentTree<T, MaxPicker, default_value>::leftest_above(uint_fast32_t, uint_fast32_t, T) const [with T = unsigned int; MaxPicker = MyLib::<lambda(unsigned int, unsigned int)>; T default_value = 0]’,
    inlined from ‘constexpr uint_fast32_t prepare(uint_fast32_t, uint_fast32_t, const std::vector<unsigned int>&, const std::vector<unsigned int>&)’ at main.cpp:211:44,
    inlined from ‘constexpr uint_fast32_t solve(uint_fast32_t, uint_fast32_t, const std::vector<unsigned int>&, std::vector<unsigned int>&)’ at main.cpp:222:33,
    inlined from ‘int main()’ at main.cpp:246:31:
main.cpp:154:56: warning: ‘candidate_index’ may be used uninitialized [-Wmaybe-uninitialized]
  154 |                                 --cur_layer, cur_index <<= 1;
      |                                              ~~~~~~~~~~^~~~~
main.cpp: In function ‘int main()’:
main.cpp:129:82: note: ‘candidate_index’ was declared here
  129 |                         uint_fast32_t candidate_layer = this->containers.size(), candidate_index;
      |                                                                                  ^~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

namespace MyLib
{
	template<typename T, class Picker, T default_value> class LiteralSegmentTree
	{
	protected:
		std::vector<std::vector<T>> containers;
	
	public:
		constexpr LiteralSegmentTree(const std::vector<T>& initializer)
		{
			containers.clear();
	
			if (initializer.size() == 0) [[unlikely]] return;
			else if (initializer.size() == 1) [[unlikely]] { containers.emplace_back(1, initializer[0]); return; }
	
			uint_fast32_t l = 0, r = 30;
			while (l + 1 < r)
			{
				const auto c = (l + r) >> 1;
				if (((uint_fast32_t)1 << c) < initializer.size())
					l = c;
				else
					r = c;
			}
	
			containers.emplace_back((uint_fast32_t)1 << r);
	
			uint_fast32_t i;
			for (i = 0; i != initializer.size(); ++i)
				containers[0][i] = initializer[i];
			for (; i != ((uint_fast32_t)1 << r); ++i)
				containers[0][i] = default_value;
	
			for (--r; r != 0; --r)
			{
				containers.emplace_back((uint_fast32_t)1 << r);
				[[assume(containers.size() >= 2)]];
				for (i = 0; i != ((uint_fast32_t)1 << r); ++i)
					containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
			}
			containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
		}
	
		constexpr LiteralSegmentTree(std::vector<T>&& initializer)
		{
			containers.clear();
	
			if (initializer.size() == 0) [[unlikely]] return;
	
			uint_fast32_t l = 0, r = 30;
			while (l + 1 < r)
			{
				const auto c = (l + r) >> 1;
				if (((uint_fast32_t)1 << c) < initializer.size())
					l = c;
				else
					r = c;
			}
	
			containers.emplace_back(std::move(initializer));
			containers[0].resize((uint_fast32_t)1 << r, default_value);
	
			uint_fast32_t i;
			for (--r; r != 0; --r)
			{
				containers.emplace_back((uint_fast32_t)1 << r);
				[[assume(containers.size() >= 2)]];
				for (i = 0; i != ((uint_fast32_t)1 << r); ++i)
					containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
			}
			containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
		}
	
		constexpr LiteralSegmentTree(const uint_fast32_t n) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, default_value)) { }
		constexpr LiteralSegmentTree(const uint_fast32_t n, const T initial_value) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, initial_value)) { }
	
		[[nodiscard]] constexpr T operator[](uint_fast32_t index) const noexcept { return containers[0][index]; }
	
		[[nodiscard]] constexpr uint_fast32_t size() const noexcept { return containers[0].size(); }
		[[nodiscard]] constexpr uint_fast32_t layer() const noexcept { return containers.size(); }
	
		constexpr T update(uint_fast32_t index, const T value) noexcept
		{
			containers[0][index] = value;
	
			index >>= 1;
			for (uint_fast32_t i = 1; i != containers.size(); ++i, index >>= 1)
				containers[i][index] = Picker()(containers[i - 1][index << 1], containers[i - 1][(index << 1) | 1]);
	
			return value;
		}
	
		[[nodiscard]] constexpr T range_pick_up(uint_fast32_t first_index, uint_fast32_t end_index) const noexcept
		{
			if (containers.size() == 0 || end_index > containers[0].size()) [[unlikely]] return default_value;
	
			T ret_l = default_value, ret_r = default_value;
			for (uint_fast32_t cur_layer = 0; first_index < end_index; first_index >>= 1, end_index >>= 1, ++cur_layer)
			{
				if (first_index & 1)
					ret_l = Picker()(ret_l, containers[cur_layer][first_index]), ++first_index;
				if (end_index & 1)
					ret_r = Picker()(containers[cur_layer][end_index - 1], ret_r);
			}
	
			return Picker()(ret_l, ret_r);
		}
	};

	template<typename T> using DefaultMaxPicker = decltype([](const T a, const T b) { return std::max<T>(a, b); });
	
	template<typename T, class MaxPicker, T default_value = std::numeric_limits<T>::lowest()>
	class MaxSegmentTree : public LiteralSegmentTree<T, MaxPicker, default_value>
	{
	public:
		constexpr MaxSegmentTree(const std::vector<T>& initializer) : LiteralSegmentTree<T, MaxPicker, default_value>(initializer) { }
		constexpr MaxSegmentTree(std::vector<T>&& initializer) : LiteralSegmentTree<T, MaxPicker, default_value>(std::move(initializer)) { }
		template<typename... Args> constexpr MaxSegmentTree(const Args... args) : LiteralSegmentTree<T, MaxPicker, default_value>(std::forward<Args>(args)...) { }
	
		[[nodiscard]] constexpr uint_fast32_t leftest_above(const uint_fast32_t first, const uint_fast32_t last, const T limit) const noexcept
		{
			[[assume(first <= last)]];
			if (this->containers.size() == 0) [[unlikely]] return 0;
	
			uint_fast32_t cur_layer, cur_index;
	
			uint_fast32_t candidate_layer = this->containers.size(), candidate_index;
			uint_fast32_t first_temp = first, last_temp = last;
			for (cur_layer = 0; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
			{
				if (first_temp & 1)
				{
					if (this->containers[cur_layer][first_temp] >= limit)
						break;
					++first_temp;
				}
				if (last_temp & 1)
				{
					[[assume(last_temp >= 1)]];
					if (this->containers[cur_layer][last_temp - 1] >= limit)
						candidate_layer = cur_layer, candidate_index = last_temp - 1;
					//--last_temp;
				}
			}
	
			if (first_temp != last_temp) cur_index = first_temp;
			else if (candidate_layer == this->containers.size()) return this->containers[0].size();
			else cur_layer = candidate_layer, cur_index = candidate_index;
	
			while (cur_layer != 0)
			{
				--cur_layer, cur_index <<= 1;
				if (this->containers[cur_layer][cur_index] < limit)
					cur_index |= 1;
			}
	
			return cur_index;
		}
	
		[[nodiscard]] constexpr uint_fast32_t rightest_above(const uint_fast32_t first, const uint_fast32_t last, const T limit) const noexcept
		{
			[[assume(first <= last)]];
			if (this->containers.size() == 0) [[unlikely]] return 0;
	
			uint_fast32_t cur_layer, cur_index;
	
			uint_fast32_t candidate_layer = this->containers.size(), candidate_index;
			uint_fast32_t first_temp = first, last_temp = last;
			for (cur_layer = 0; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
			{
				if (last_temp & 1)
				{
					[[assume(last_temp >= 1)]];
					if (this->containers[cur_layer][last_temp - 1] >= limit)
						break;
					//--last_temp;
				}
				if (first_temp & 1)
				{
					if (this->containers[cur_layer][first_temp] >= limit)
						candidate_layer = cur_layer, candidate_index = first_temp;
					++first_temp;
				}
			}
	
			if (first_temp != last_temp) cur_index = last_temp - 1;
			else if (candidate_layer == this->containers.size()) return this->containers[0].size();
			else cur_layer = candidate_layer, cur_index = candidate_index;
	
			while (cur_layer != 0)
			{
				--cur_layer, cur_index <<= 1;
				if (this->containers[cur_layer][cur_index | 1] >= limit)
					cur_index |= 1;
			}
	
			return cur_index;
		}
	};
}

[[nodiscard]] static inline constexpr uint_fast32_t prepare(const uint_fast32_t N, const uint_fast32_t M, const std::vector<uint_least32_t>& S, const std::vector<uint_least32_t>& T) noexcept
{
	[[assume(std::is_sorted(S.begin(), S.end()))]];
	MyLib::MaxSegmentTree<uint_least32_t, MyLib::DefaultMaxPicker<uint_least32_t>, 0> unused_S(S);

	for (uint_fast32_t x = 0; x != M; ++x)
	{
		const auto index = unused_S.leftest_above(0, N, T[x]);
		if (index >= N) return x;
		unused_S.update(index, 0);
	}

	return M;
}

[[nodiscard]] static inline constexpr uint_fast32_t solve(const uint_fast32_t N, const uint_fast32_t M, const std::vector<uint_least32_t>& S, std::vector<uint_least32_t>& T) noexcept
{
	[[assume(std::is_sorted(S.begin(), S.end()))]];
	const uint_fast32_t x = prepare(N, M, S, T);
	std::sort(T.begin(), T.begin() + x);
	uint_fast32_t ans = 0;
	for (uint_fast32_t i = 0, j = 0; j != x; ++i, ++j)
	{
		while (S[i] < T[j]) ++i;
		ans = std::max<uint_fast32_t>(ans, S[i] - T[j]);
	}

	return ans;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);

	uint_fast32_t N, M;
	std::cin >> N >> M;
	std::vector<uint_least32_t> S(N), T(M);
	for (auto& s : S) std::cin >> s;
	for (auto& t : T) std::cin >> t;

	std::sort(S.begin(), S.end());
	std::cout << solve(N, M, S, T) << '\n';
	return 0;
}
0