結果

問題 No.905 Sorted?
ユーザー elpheelphe
提出日時 2024-12-25 12:18:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 3,282 bytes
コンパイル時間 1,714 ms
コンパイル使用メモリ 100,404 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-25 12:18:24
合計ジャッジ時間 3,727 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 4 ms
5,248 KB
testcase_08 AC 55 ms
5,248 KB
testcase_09 AC 38 ms
5,248 KB
testcase_10 AC 53 ms
5,248 KB
testcase_11 AC 34 ms
5,248 KB
testcase_12 AC 36 ms
5,248 KB
testcase_13 AC 44 ms
5,248 KB
testcase_14 AC 61 ms
5,248 KB
testcase_15 AC 39 ms
5,248 KB
testcase_16 AC 55 ms
5,248 KB
testcase_17 AC 54 ms
5,248 KB
testcase_18 AC 42 ms
5,248 KB
testcase_19 RE -
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

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 (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