#1026311 (C++17) No.2930 Larger Mex

提出ソース

結果

問題	No.2930 Larger Mex
ユーザー	elphe
提出日時	2024-11-12 17:39:45
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	62 ms / 2,000 ms
コード長	3,812 bytes
コンパイル時間	1,300 ms
コンパイル使用メモリ	85,328 KB
実行使用メモリ	7,020 KB
最終ジャッジ日時	2024-11-12 17:39:54
合計ジャッジ時間	9,463 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	6 ms 6,816 KB
testcase_01	AC	6 ms 6,816 KB
testcase_02	AC	5 ms 6,816 KB
testcase_03	AC	6 ms 6,816 KB
testcase_04	AC	6 ms 6,820 KB
testcase_05	AC	5 ms 6,820 KB
testcase_06	AC	6 ms 6,820 KB
testcase_07	AC	6 ms 6,820 KB
testcase_08	AC	49 ms 6,820 KB
testcase_09	AC	47 ms 6,816 KB
testcase_10	AC	52 ms 7,020 KB
testcase_11	AC	40 ms 6,820 KB
testcase_12	AC	58 ms 6,920 KB
testcase_13	AC	56 ms 6,904 KB
testcase_14	AC	58 ms 6,916 KB
testcase_15	AC	51 ms 6,820 KB
testcase_16	AC	51 ms 6,820 KB
testcase_17	AC	61 ms 6,896 KB
testcase_18	AC	50 ms 6,816 KB
testcase_19	AC	57 ms 6,820 KB
testcase_20	AC	59 ms 6,816 KB
testcase_21	AC	62 ms 6,816 KB
testcase_22	AC	56 ms 6,888 KB
testcase_23	AC	52 ms 6,820 KB
testcase_24	AC	58 ms 6,820 KB
testcase_25	AC	61 ms 6,892 KB
testcase_26	AC	50 ms 6,820 KB
testcase_27	AC	42 ms 6,816 KB
testcase_28	AC	45 ms 6,816 KB
testcase_29	AC	46 ms 6,832 KB
testcase_30	AC	47 ms 6,816 KB
testcase_31	AC	42 ms 6,820 KB
testcase_32	AC	52 ms 6,820 KB
testcase_33	AC	52 ms 6,820 KB
testcase_34	AC	56 ms 6,900 KB
testcase_35	AC	37 ms 6,820 KB
testcase_36	AC	54 ms 6,876 KB
testcase_37	AC	54 ms 6,820 KB
testcase_38	AC	61 ms 6,816 KB
testcase_39	AC	58 ms 6,816 KB
testcase_40	AC	61 ms 6,820 KB
testcase_41	AC	49 ms 6,820 KB
testcase_42	AC	45 ms 6,824 KB
testcase_43	AC	44 ms 6,832 KB
testcase_44	AC	48 ms 6,852 KB
testcase_45	AC	48 ms 6,820 KB
testcase_46	AC	57 ms 6,816 KB
testcase_47	AC	56 ms 6,820 KB
testcase_48	AC	43 ms 6,820 KB
testcase_49	AC	59 ms 6,904 KB
testcase_50	AC	52 ms 6,816 KB
testcase_51	AC	60 ms 6,920 KB
testcase_52	AC	61 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <cstdint>
#include <vector>

using namespace std;

template<typename T> class SegmentTree
{
protected:
	vector<vector<T>> containers;
	const T default_value;
	T(* const pick_up)(T, T);

public:
	SegmentTree(T(* const pick_up)(T, T), const vector<T>& initializer, const T default_value) : default_value(default_value), pick_up(pick_up)
	{
		containers.clear();

		if (initializer.size() == 0) return;

		size_t L;
		for (L = 1; L < initializer.size(); L <<= 1);
		containers.emplace_back(L);

		size_t i;
		for (i = 0; i != initializer.size(); ++i)
			containers[0][i] = initializer[i];
		for (; i != L; ++i)
			containers[0][i] = default_value;

		for (L >>= 1; L != 0; L >>= 1)
		{
			containers.emplace_back(L);
			for (i = 0; i != L; ++i)
				containers[containers.size() - 1][i] = pick_up(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
		}
	}

	SegmentTree(T(* const pick_up)(T, T), vector<T>&& initializer, const T default_value) : default_value(default_value), pick_up(pick_up)
	{
		containers.clear();

		if (initializer.size() == 0) return;

		size_t L;
		for (L = 1; L < initializer.size(); L <<= 1);
		containers.emplace_back(initializer);
		containers[0].resize(L, default_value);

		size_t i;
		for (L >>= 1; L != 0; L >>= 1)
		{
			containers.emplace_back(L);
			for (i = 0; i != L; ++i)
				containers[containers.size() - 1][i] = pick_up(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
		}
	}

	T operator[](size_t index) const noexcept { return containers[0][index]; }

	size_t size() const noexcept { return containers[0].size(); }
	size_t layer() const noexcept { return containers.size(); }

	virtual T update(size_t index, const T value) noexcept
	{
		containers[0][index] = value;

		index >>= 1;
		for (size_t i = 1; i != containers.size(); ++i, index >>= 1)
			containers[i][index] = pick_up(containers[i - 1][index << 1], containers[i - 1][(index << 1) | 1]);

		return value;
	}

	virtual T range_pick_up(size_t first_index, size_t end_index, size_t cur_layer = 0) const noexcept
	{
		if (first_index >= end_index || end_index > containers[cur_layer].size()) return default_value;
		if (first_index + 1 == end_index) return containers[cur_layer][first_index];

		if (first_index & 1)
		{
			if (end_index & 1)
			{
				if (first_index + 2 != end_index)
					return pick_up(pick_up(containers[cur_layer][first_index], containers[cur_layer][end_index - 1]), range_pick_up((first_index + 1) >> 1, end_index >> 1, cur_layer + 1));
				else
					return pick_up(containers[cur_layer][first_index], containers[cur_layer][end_index - 1]);
			}
			else
				return pick_up(containers[cur_layer][first_index], range_pick_up((first_index + 1) >> 1, end_index >> 1, cur_layer + 1));
		}
		else
		{
			if (end_index & 1)
				return pick_up(containers[cur_layer][end_index - 1], range_pick_up(first_index >> 1, end_index >> 1, cur_layer + 1));
			else
				return range_pick_up(first_index >> 1, end_index >> 1, cur_layer + 1);
		}
	}
};

constexpr uint32_t min(const uint32_t a, const uint32_t b) noexcept
{
	if (a < b) return a;
	else return b;
}

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

	uint32_t N, M, i;
	cin >> N >> M;
	vector<uint32_t> A(N);
	for (i = 0; i != N; ++i) cin >> A[i];

	SegmentTree<uint32_t> st(min, vector<uint32_t>(200001, 0), UINT32_MAX);
	vector<int32_t> ans_imos(N + 2, 0);
	for (uint32_t l = 0, r = 0; r != N; ++r)
	{
		st.update(A[r], st[A[r]] + 1);
		if (st.range_pick_up(0, M) != 0)
		{
			while (l <= r && (A[l] >= M || st[A[l]] != 1))
				st.update(A[l], st[A[l]] - 1), ++l;
			++ans_imos[r - l + 1], --ans_imos[r + 2];
		}
	}

	for (i = 1; i <= N; ++i)
		ans_imos[i] += ans_imos[i - 1], cout << ans_imos[i] << '\n';

	return 0;
}

yukicoder

結果

テストケース

ソースコード