結果
問題 | No.905 Sorted? |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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 ";elsecout << "0 ";if (st_g.range_pick_up(l[i], r[i]))cout << "1\n";elsecout << "0\n";}return 0;}