#376380 (C++17) No.878 Range High-Element Query

• 問題: No.878 Range High-Element Query
• ユーザー: rsk0315
• 提出日時: 2019-09-06 21:56:05
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 5,594 bytes
• コンパイル時間: 770 ms
• コンパイル使用メモリ: 65,920 KB
• 実行使用メモリ: 10,368 KB
• 最終ジャッジ日時: 2024-06-24 17:41:30
• 合計ジャッジ時間: 2,097 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-

ソースコード

#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <tuple>

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
// constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }

template <
  typename Monoid,
  typename Container = std::vector<typename Monoid::first_type>
>
class basic_segment_tree {
public:
  using size_type = size_t;
  using first_type = typename Monoid::first_type;
  using second_type = typename Monoid::second_type;
  using value_type = first_type;
  using binary_operation = typename Monoid::binary_operation;
  using external_binary_operation = typename Monoid::external_binary_operation;
  using container = Container;

private:
  size_type M_base_size;
  binary_operation M_op1;
  external_binary_operation M_op2;
  container M_c;

  template <typename Predicate>
  size_type M_search_root(Predicate pred, value_type& x) const {
    size_type n = M_base_size;
    size_type l = n;
    size_type r = n+n;
    size_type v = r;
    std::vector<size_type> rs;
    x = M_op1.identity;
    while (l < r) {
      if (l & 1) {
        if (!pred(M_op1(x, M_c[l]))) return l;
        x = M_op1(x, M_c[l++]);
      }
      if (r & 1) rs.push_back(--r);
      l >>= 1;
      r >>= 1;
    }
    while (!rs.empty()) {
      size_type r = rs.back();
      rs.pop_back();
      if (!pred(M_op1(x, M_c[r]))) return r;
      x = M_op1(x, M_c[r]);
    }
    return v;
  }

  template <typename Predicate>
  size_type M_search_leaf(Predicate pred, size_type v, value_type& x) const {
    size_type n = M_base_size;
    while (v < n) {
      size_type c = v << 1;
      if (pred(M_op1(x, M_c[c]))) {
        x = M_op1(x, M_c[c]);
        c |= 1;
      }
      v = c;
    }
    return v - n;
  }

public:
  basic_segment_tree() = default;
  basic_segment_tree(basic_segment_tree const&) = default;
  basic_segment_tree(basic_segment_tree&&) = default;

  basic_segment_tree(size_type n, first_type const& x = binary_operation().identity):
    M_base_size(n),
    M_op1(binary_operation()),
    M_op2(external_binary_operation()),
    M_c(n+n, x)
  {
    for (size_type i = n; i--;)
      M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
  }

  template <typename InputIt>
  basic_segment_tree(InputIt first, InputIt last):
    M_op1(binary_operation()), M_op2(external_binary_operation())
  { assign(first, last); }

  basic_segment_tree& operator =(basic_segment_tree const&) = default;
  basic_segment_tree& operator =(basic_segment_tree&&) = default;

  void assign(size_type n, value_type const& x) {
    M_base_size = n;
    M_c.assign(n+n, x);
    for (size_type i = n; i--;)
      M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
  }
  template <typename InputIt>
  void assign(InputIt first, InputIt last) {
    container tmp(first, last);
    M_base_size = tmp.size();
    M_c.resize(M_base_size);
    M_c.insert(M_c.end(), tmp.begin(), tmp.end());
    for (size_type i = M_base_size; i--;)
      M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
  }

  void modify(size_type i, second_type const& x) {
    i += M_base_size;
    M_c[i] = M_op2(M_c[i], x);
    while (i > 1) {
      i >>= 1;
      M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
    }
  }

  void assign_at(size_type i, value_type const& x) {
    i += M_base_size;
    M_c[i] = x;
    while (i > 1) {
      i >>= 1;
      M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
    }
  }

  value_type const& operator [](size_type i) const { return M_c[i + M_base_size]; }

  value_type accumulate(size_type l, size_type r) {
    first_type resl = M_op1.identity;
    first_type resr = resl;
    l += M_base_size;
    r += M_base_size;
    while (l < r) {
      if (l & 1) resl = M_op1(resl, M_c[l++]);
      if (r & 1) resr = M_op1(M_c[--r], resr);
      l >>= 1;
      r >>= 1;
    }
    return M_op1(resl, resr);
  }

  template <typename Predicate>
  std::pair<size_type, value_type> partition_point(Predicate pred) const {
    value_type value;
    size_type root = M_search_root(pred, value);
    size_type bound = M_search_leaf(pred, root, value);
    return {bound, value};
  }
};

template <typename Tp>
struct range_high_query {
  using first_type = std::tuple<Tp, size_t>;  // max (self), count
  using second_type = Tp;
  struct binary_operation {
    first_type identity{};
    first_type operator ()(first_type const& x, first_type const& y) const {
      int x0, y0;
      size_t x1, y1;
      std::tie(x0, x1) = x;
      std::tie(y0, y1) = y;
      if (x0 < y0) {
        return {y0, x1+y1};
      } else {
        return {x0, x1};
      }
    }
  };
  struct external_binary_operation {
    first_type operator ()(first_type const& x, second_type const&) const {
      return x;
    }
  };
};

int main() {
  size_t n, q;
  scanf("%zu %zu", &n, &q);

  std::vector<std::tuple<int, size_t>> a(n);
  for (auto& ai: a) {
    int tmp;
    scanf("%d", &tmp);
    ai = std::make_tuple(tmp, 1);
  }

  basic_segment_tree<range_high_query<int>> st(a.begin(), a.end());
  for (size_t i = 0; i < q; ++i) {
    size_t l, r;
    scanf(" 1 %zu %zu", &l, &r);
    --l, --r;
    // fprintf(stderr, "[%zu, %zu)\n", l, r+1);
    printf("%zu\n", std::get<size_t>(st.accumulate(l, r+1)));
  }

  // for (size_t i = 0; i < n; ++i)
  //   for (size_t j = 0; j <= i; ++j) {
  //     int x0;
  //     size_t x1;
  //     std::tie(x0, x1) = st.accumulate(j, i+1);
  //     fprintf(stderr, "[%zu, %zu): %d, %zu\n",
  //             j, i+1, x0, x1);
  //   }
}