結果

問題 No.905 Sorted?
ユーザー elpheelphe
提出日時 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0