Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3594

Problem Lang User Status Time Memory
Static RMQ cpp KoD AC 993 ms 9.30 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.63 MiB
max_random_00 AC 977 ms 9.11 MiB
max_random_01 AC 986 ms 9.12 MiB
max_random_02 AC 988 ms 8.88 MiB
max_random_03 AC 993 ms 9.30 MiB
max_random_04 AC 983 ms 9.09 MiB
random_00 AC 801 ms 8.25 MiB
random_01 AC 824 ms 8.51 MiB
random_02 AC 639 ms 3.59 MiB
random_03 AC 164 ms 6.34 MiB
random_04 AC 246 ms 6.17 MiB
small_00 AC 7 ms 0.59 MiB
small_01 AC 8 ms 0.60 MiB
small_02 AC 6 ms 0.63 MiB
small_03 AC 6 ms 0.66 MiB
small_04 AC 8 ms 0.62 MiB
small_05 AC 8 ms 0.62 MiB
small_06 AC 8 ms 0.66 MiB
small_07 AC 6 ms 0.66 MiB
small_08 AC 8 ms 0.62 MiB
small_09 AC 8 ms 0.66 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 segment_tree { public: using value_type = typename T::value_type; using effector_type = typename T::effector_type; using value_operation = typename T::value_operation; using merge_operation = typename T::merge_operation; private: int size; const value_operation op1; const merge_operation op2; std::vector<value_type> node; public: segment_tree(): op1(value_operation()), op2(merge_operation()) { } segment_tree(int size_, const value_type &initial_ = value_operation().identity): op1(value_operation()), op2(merge_operation()) { init(size_, initial_); } segment_tree(const std::vector<value_type> &node_): op1(value_operation()), op2(merge_operation()) { build(node_); } void init(int size_, const value_type &initial_ = value_operation().identity) { size = 1; while (size < size_) { size <<= 1; } node.assign(size << 1, initial_); } void build(const std::vector<value_type> &node_) { init(node_.size()); assign(node_.begin(), node_.end(), 0); } void modify(int i, const effector_type &x) { i += size; node[i] = op2(node[i], x); while (i > 1) { i >>= 1; node[i] = op1(node[i << 1 | 0], node[i << 1 | 1]); } } template <class U> void modify(U begin, U end, int i) { i += size; while (begin != end) { node[i] = op2(node[i], *begin); ++i; ++begin; } for (int k = size - 1; k > 0; --k) { node[k] = op1(node[k << 1 | 0], node[k << 1 | 1]); } } void assign(int i, const value_type &x) { i += size; node[i] = x; while (i > 1) { i >>= 1; node[i] = op1(node[i << 1 | 0], node[i << 1 | 1]); } } template <class U> void assign(U begin, U end, int i) { i += size; while (begin != end) { node[i] = *begin; ++i; ++begin; } for (int k = size - 1; k > 0; --k) { node[k] = op1(node[k << 1 | 0], node[k << 1 | 1]); } } value_type operator [] (int i) const { return node[i + size]; } value_type fold(int l, int r) const { l += size; r += size; value_type resl = op1.identity; value_type resr = op1.identity; while (l < r) { if (l & 1) { resl = op1(resl, node[l++]); } if (r & 1) { resr = op1(node[--r], resr); } l >>= 1; r >>= 1; } return op1(resl, resr); } }; int main() { int N, Q; std::cin >> N >> Q; std::vector<int> A(N); for (int &x: A) { std::cin >> x; } segment_tree<range_min_single_assign<int>> seg(A); for (int i: range(0, Q)) { int l, r; std::cin >> l >> r; std::cout << seg.fold(l, r) << '\n'; } return 0; }