結果

問題 No.3298 K-th Slime
コンテスト
ユーザー tomolatoon
提出日時 2025-10-05 18:09:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 188 ms / 2,000 ms
コード長 7,704 bytes
コンパイル時間 3,387 ms
コンパイル使用メモリ 232,992 KB
実行使用メモリ 13,056 KB
最終ジャッジ日時 2025-10-05 18:10:03
合計ジャッジ時間 5,847 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bit>
#include <charconv>
#include <cmath>
#include <cstdint>
#include <deque>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numbers>
#include <numeric>
#include <queue>
#include <ranges>
#include <set>
#include <span>
#include <stack>
#include <string>
#include <string_view>
#include <tuple>
#include <vector>

//#include <bits/stdc++.h>

#ifdef DEBUG
# include <format>
# include <print>
#endif

namespace tomolatoon
{
	using namespace std::views;

	using std::cin;
	using std::cout;
	using std::endl;

	using std::array;
	using std::deque;
	using std::map;
	using std::multimap;
	using std::multiset;
	using std::pair;
	using std::queue;
	using std::set;
	using std::span;
	using std::stack;
	using std::string;
	using std::string_view;
	using std::tuple;
	using std::vector;
	using std::ranges::subrange;

	template <class T>
	using vec = vector<T>;

	using uint = uint32_t;

	using ull = uint64_t;
	using ll  = int64_t;

	// clang-format off
	using std::ranges::all_of;
	using std::ranges::any_of;
	using std::ranges::none_of;
	using std::ranges::for_each;
	using std::ranges::for_each_n;
	using std::ranges::find;
	using std::ranges::find_if;
	using std::ranges::find_if_not;
	using std::ranges::find_end;
	using std::ranges::find_first_of;
	using std::ranges::adjacent_find;
	using std::ranges::count;
	using std::ranges::count_if;
	using std::ranges::mismatch;
	using std::ranges::equal;
	using std::ranges::search;
	using std::ranges::search_n;
	// clang-format on

	using std::ranges::sort;
	using std::ranges::stable_sort;
	using std::ranges::unique;

	using std::ranges::max_element;
	using std::ranges::min_element;

	using std::ranges::binary_search;
	using std::ranges::equal_range;
	using std::ranges::lower_bound;
	using std::ranges::upper_bound;

	using std::ranges::next_permutation;
	using std::ranges::prev_permutation;

	using std::ranges::begin;
	using std::ranges::distance;
	using std::ranges::end;
	using std::ranges::ssize;
	using std::ranges::swap;

	// for (auto i : iota(0, n)) を使う
	namespace rng = std::ranges;

	using std::back_inserter;
	using std::front_inserter;
	using std::inserter;

	using namespace std::placeholders;

	void yn(bool f)
	{
		cout << (f ? "Yes" : "No") << endl;
	}

	string yns(bool f)
	{
		return f ? "Yes" : "No";
	}

	struct P
	{
		using type = ll;

		type i;
		type j;

		P moved(type id, type jd) const
		{
			return {i + id, j + jd};
		}

		P moved(P pd) const
		{
			return moved(pd.i, pd.j);
		}

		template <class T>
		T& operator[](vec<vec<T>>& v) const
		{
			return v[i][j];
		}

		char& operator[](vec<string>& v) const
		{
			return v[i][j];
		}

		friend bool operator==(const P& lhs, const P& rhs)
		{
			return lhs.i == rhs.i && lhs.j == rhs.j;
		}

		friend auto operator<=>(const P& lhs, const P& rhs)
		{
			return lhs.i != rhs.i ? lhs.i <=> rhs.i : lhs.j <=> rhs.j;
		}
	};

	// clang-format off
	auto in_f = [](P::type h, P::type w) { return [=](P p) { return 0 <= p.i && p.i < h && 0 <= p.j && p.j < w; }; };

	static const auto P4 = array<P, 4>{P{-1,  0}, P{ 0, -1}, P{ 1,  0}, P{ 0,  1}};
	static const auto P8 = array<P, 8>{P{-1,  0}, P{-1, -1}, P{ 0, -1}, P{ 1, -1}, P{ 1,  0}, P{ 1,  1}, P{ 0,  1}, P{-1,  1}};
	// clang-format on

	ll pow(ll base, ll pow)
	{
		ll res = 1;
		for (auto i : iota(0, pow))
		{
			res *= base;
		}
		return res;
	}

	template <class T>
	T shared_length(T l1, T r1, T l2, T r2)
	{
		return rng::max(0, rng::min(r1, r2) - rng::max(l1, l2));
	}

	namespace detail
	{
		using namespace std::ranges;

		template <input_range R, std::output_iterator<std::pair<range_value_t<R>, size_t>> I>
		requires std::copyable<range_value_t<R>> && std::equality_comparable<range_value_t<R>>
		void run_length(R&& t, I out)
		{
			using pair = std::pair<range_value_t<R>, size_t>;

			auto it = begin(t);
			auto e  = end(t);

			if (it == e)
			{
				return;
			}

			size_t           size = 1;
			range_value_t<R> prev = *it;

			++it;

			for (; it != e; ++it)
			{
				if (*it == prev)
				{
					++size;
				}
				else
				{
					*out++ = pair(std::move(prev), size);
					prev   = *it;
					size   = 1;
				}
			}

			*out++ = pair(std::move(prev), size);
		}
	} // namespace detail

	using detail::run_length;

	namespace detail
	{
		template <size_t N>
		struct get
		{
			template <class T>
			constexpr decltype(auto) operator()(T&& t) const noexcept(noexcept(std::get<N>(t)))
			{
				return std::get<N>(t);
			}
		};
	} // namespace detail

	template <size_t N>
	inline constexpr auto get = detail::get<N>{};

} // namespace tomolatoon

#include <atcoder/all>

namespace tomolatoon
{
	using atcoder::dsu;
} // namespace tomolatoon

namespace tomolatoon
{
	void solve()
	{
		ll n, k, q;
		cin >> n >> k >> q;

		map<ll, size_t> st;
		for (ll i : iota(0, n))
		{
			ll a;
			cin >> a;

			if (auto it = st.find(a); it == st.end())
			{
				st[a] = 1;
			}
			else
			{
				++it->second;
			}
		}

		ll idx = 0;
		ll key = 0;
		for (auto&& [acc, cur] = tuple{0ll, st.begin()}; auto i : iota(0ll, ssize(st)))
		{
			if (acc + cur->second >= k)
			{
				key = cur->first;
				idx = rng::max(0ll, k - acc - 1);
				break;
			}

			acc += cur->second;
			++cur;
		}

		// insert with update
		auto iwu = [&](ll v) {
			auto ih = [&](ll v) {
				if (auto it = st.find(v); it == st.end())
				{
					st.insert({v, 1});
				}
				else
				{
					++st[v];
				}
			};

			if (key == -1)
			{
				ih(v);
				key = (st.begin())->first;
				idx = 0;
				return;
			}

			if (key == -2)
			{
				ih(v);
				key = (--st.end())->first;
				idx = 0;
				return;
			}

			if (v >= key)
			{
				ih(v);
			}
			else
			{
				if (idx == 0)
				{
					if (k == 0)
					{
						ih(v);
						key = v;
						idx = 0;
					}
					else
					{
						auto it     = st.find(key);
						auto tmpkey = (--it)->first;

						if (v <= tmpkey)
						{
							ih(v);
							key = tmpkey;
							idx = st[tmpkey] - 1;
						}
						else
						{
							ih(v);
							key = v;
							idx = 0;
						}
					}
				}
				else
				{
					--idx;
					ih(v);
				}
			}
		};

		// erase with update
		auto ewu = [&](ll v) {
			auto eh = [&](ll v) {
				if (auto it = st.find(v); it->second == 1)
				{
					st.erase(it);
				}
				else
				{
					--it->second;
				}
			};

			if (v > key)
			{
				eh(v);
			}
			else // if (v <= key)
			{
				if (st[v] == idx + 1)
				{
					if (++st.find(v) == st.end())
					{
						eh(v);
						key = -2;
						idx = 0;
					}

					/*if (st.size() == 1)
					{
						if (st.begin()->second == 1)
						{
							eh(v);
							key = -1;
							idx = 0;
						}
						else
						{
							eh(v);
							key = -2;
							idx = 0;
						}
					}*/
					else
					{
						auto nkey = (++st.find(v))->first;
						eh(v);
						key = nkey;
						idx = 0;
					}
				}
				else
				{
					eh(v);
				}
			}
			/*else
			{
			    if (st[v] == idx + 1)
			    {
			        auto nkey = (++st.find(v))->first;
			        eh(v);
			        key = nkey;
			        idx = 0;
			    }
			    else
			    {
			        ++idx;
			        eh(v);
			    }
			}*/
		};

		for (ll i : iota(0, q))
		{
			ll o;
			cin >> o;

			switch (o)
			{
			case 1:
				{
					ll x;
					cin >> x;
					iwu(x);
				}
				break;
			case 2:
				{
					ll y;
					cin >> y;
					ll ikey = key + y;
					ewu(key);
					iwu(ikey);
				}
				break;
			case 3:
				{
					cout << key << endl;
				}
				break;
			}
		}
	}
} // namespace tomolatoon

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(16);

	tomolatoon::solve();

	std::cout << std::flush;
}
0