Submit Info #3596

Problem Lang User Status Time Memory
Static RMQ cpp KoD AC 717 ms 41.58 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.72 MiB
max_random_00 AC 702 ms 41.39 MiB
max_random_01 AC 694 ms 41.51 MiB
max_random_02 AC 717 ms 41.26 MiB
max_random_03 AC 692 ms 41.58 MiB
max_random_04 AC 692 ms 41.39 MiB
random_00 AC 560 ms 32.56 MiB
random_01 AC 594 ms 38.25 MiB
random_02 AC 395 ms 6.46 MiB
random_03 AC 170 ms 35.17 MiB
random_04 AC 200 ms 22.92 MiB
small_00 AC 2 ms 0.67 MiB
small_01 AC 4 ms 0.70 MiB
small_02 AC 5 ms 0.68 MiB
small_03 AC 7 ms 0.70 MiB
small_04 AC 3 ms 0.68 MiB
small_05 AC 3 ms 0.68 MiB
small_06 AC 4 ms 0.68 MiB
small_07 AC 4 ms 0.72 MiB
small_08 AC 0 ms 0.68 MiB
small_09 AC 4 ms 0.69 MiB

#include <iostream> #include <algorithm> #include <utility> #include <vector> #include <numeric> #include <functional> #include <tuple> template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return true; } return false; } template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return true; } return false; } // [l, r) from l to r struct range { struct itr { int i; constexpr itr(int i_): i(i_) { } constexpr void operator ++ () { ++i; } constexpr int operator * () const { return i; } constexpr bool operator != (itr x) const { return i != x.i; } }; const itr l, r; constexpr range(int l_, int r_): l(std::min<int>(l_, r_)), r(r_) {} constexpr itr begin() const { return l; } constexpr itr end() const { return r; } }; // [l, r) from r to l struct revrange { struct itr { int i; constexpr itr(int i_): i(i_) { } constexpr void operator ++ () { --i; } constexpr int operator * () const { return i; } constexpr bool operator != (itr x) const { return i != x.i; } }; const itr r, l; constexpr revrange(int l_, int r_): r(std::max<int>(l_, r_) - 1), l(l_ - 1) {} constexpr itr begin() const { return r; } constexpr itr end() const { return l; } }; template <class T> inline T scan() { T res; std::cin >> res; return res; } #include <limits> template <class T> struct range_min_single_assign { using value_type = T; using effector_type = T; struct value_operation { value_type identity = std::numeric_limits<T>::max(); value_type operator () (const value_type &x, const value_type &y) const { return x < y ? x : y; } }; struct merge_operation { value_type operator () (const value_type &x, const effector_type &y) const { return y; } }; }; template <class T> class disjoint_sparse_table { public: using value_type = typename T::value_type; using value_operation = typename T::value_operation; private: const value_operation op; std::vector<std::vector<value_type>> table; public: disjoint_sparse_table(): op(value_operation()) { } disjoint_sparse_table(const std::vector<value_type> &table_): op(value_operation()) { build(table_); } void build(const std::vector<value_type> &table_) { int height = 0, size = table_.size(); while ((1 << height) < size) { ++height; } if (size == 1) { ++height; } table.assign(height, std::vector<value_type>(size)); for (int i = 0; i < size; ++i) { table[0][i] = table_[i]; } for (int i = 1; i < height; ++i) { int bit = (1 << i); for (int l = 0; l < size; l += (bit << 1)) { int m = (l + bit < size ? l + bit : size); table[i][m - 1] = table_[m - 1]; for (int j = m - 2; j >= l; --j) { table[i][j] = op(table_[j], table[i][j + 1]); } if (m >= size) { continue; } int r = (m + bit < size ? m + bit : size); table[i][m] = table_[m]; for (int j = m + 1; j < r; ++j) { table[i][j] = op(table[i][j - 1], table_[j]); } } } } value_type fold(int l, int r) const { if (l >= --r) { return table[0][l]; } else { int h = 31 - __builtin_clz(l ^ r); return op(table[h][l], table[h][r]); } } }; int main() { int N, Q; std::cin >> N >> Q; std::vector<int> A(N); for (int &x: A) { std::cin >> x; } disjoint_sparse_table<range_min_single_assign<int>> st(A); for (int i: range(0, Q)) { int l, r; std::cin >> l >> r; std::cout << st.fold(l, r) << '\n'; } return 0; }