結果

問題 No.905 Sorted?
ユーザー elphe
提出日時 2024-12-25 12:26:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 69 ms / 2,000 ms
コード長 3,308 bytes
コンパイル時間 1,438 ms
コンパイル使用メモリ 100,324 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-25 12:26:39
合計ジャッジ時間 2,880 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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) const noexcept
	{
		if (containers.size() == 0 || end_index > containers[0].size()) return default_value;

		T ret = default_value;
		for (size_t cur_layer = 0; first_index < end_index; first_index >>= 1, end_index >>= 1, ++cur_layer)
		{
			if (first_index & 1)
				ret = pick_up(ret, containers[cur_layer][first_index]), ++first_index;
			if (end_index & 1)
				ret = pick_up(ret, containers[cur_layer][end_index - 1]);
		}

		return ret;
	}
};

constexpr bool bool_and(const bool a, const bool b) noexcept
{
	return a && b;
}

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

	int32_t N, Q, i;
	cin >> N;
	vector<int64_t> A(N);
	for (i = 0; i != N; ++i) cin >> A[i];

	cin >> Q;
	vector<int32_t> l(Q), r(Q);
	for (i = 0; i != Q; ++i) cin >> l[i] >> r[i];

	vector<bool> check_f(N - 1), check_g(N - 1);
	for (i = 0; i != N - 1; ++i)
	{
		check_f[i] = A[i] <= A[i + 1];
		check_g[i] = A[i] >= A[i + 1];
	}

	SegmentTree<bool> st_f(bool_and, move(check_f), true), st_g(bool_and, move(check_g), true);
	for (i = 0; i != Q; ++i)
	{
		if (st_f.range_pick_up(l[i], r[i]))
			cout << "1 ";
		else
			cout << "0 ";

		if (st_g.range_pick_up(l[i], r[i]))
			cout << "1\n";
		else
			cout << "0\n";
	}

	return 0;
}
0