結果

問題 No.2930 Larger Mex
コンテスト
ユーザー elphe
提出日時 2024-11-12 17:39:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 3,812 bytes
コンパイル時間 1,074 ms
コンパイル使用メモリ 83,852 KB
最終ジャッジ日時 2025-02-25 04:00:40
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0