proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/cartesian_tree/value_based_interval.test.cpp

Depends on

Code

// competitive-verifier: STANDALONE
// Source: https://atcoder.jp/contests/abc311/tasks/abc311_g

#include <iostream>
#include <limits>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/cartesian_tree.hpp"
#include "tools/chmax.hpp"
#include "tools/chmin.hpp"
#include "tools/cumsum2d.hpp"

using ll = long long;

ll solve(const int N, const int M, const std::vector<std::vector<int>>& A) {
  const tools::cumsum2d<int> sum(A);

  auto answer = std::numeric_limits<ll>::min();
  for (int r1 = 0; r1 < N; ++r1) {
    std::vector<int> row(M, std::numeric_limits<int>::max());
    for (int r2 = r1 + 1; r2 <= N; ++r2) {
      for (int c = 0; c < M; ++c) {
        tools::chmin(row[c], A[r2 - 1][c]);
      }
      const tools::cartesian_tree cartesian_tree(row);
      for (int c = 0; c < M; ++c) {
        const auto& [c1, c2] = cartesian_tree.get_vertex(c).value_based_interval;
        tools::chmax(answer, static_cast<ll>(row[c]) * sum.query(r1, r2, c1, c2));
      }
    }
  }

  return answer;
}

void sample01() {
  const int N = 3;
  const int M = 3;
  const std::vector<std::vector<int>> A = {
    {5, 4, 3},
    {4, 3, 2},
    {3, 2, 1},
  };
  assert_that(solve(N, M, A) == 48);
}

void sample02() {
  const int N = 4;
  const int M = 5;
  const std::vector<std::vector<int>> A = {
    {3, 1, 4, 1, 5},
    {9, 2, 6, 5, 3},
    {5, 8, 9, 7, 9},
    {3, 2, 3, 8, 4},
  };
  assert_that(solve(N, M, A) == 231);
}

void sample03() {
  const int N = 6;
  const int M = 6;
  const std::vector<std::vector<int>> A = {
    {1, 300, 300, 300, 300, 300},
    {300, 1, 300, 300, 300, 300},
    {300, 300, 1, 300, 300, 300},
    {300, 300, 300, 1, 300, 300},
    {300, 300, 300, 300, 1, 300},
    {300, 300, 300, 300, 300, 1},
  };
  assert_that(solve(N, M, A) == 810000);
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  sample01();
  sample02();
  sample03();

  return 0;
}

#line 1 "tests/cartesian_tree/value_based_interval.test.cpp"
// competitive-verifier: STANDALONE
// Source: https://atcoder.jp/contests/abc311/tasks/abc311_g

#include <iostream>
#include <limits>
#include <vector>
#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/cartesian_tree.hpp"



#include <cassert>
#include <functional>
#include <iterator>
#include <stack>
#include <ranges>
#include <utility>
#line 1 "tools/getter_result.hpp"



#include <type_traits>

namespace tools {
  template <typename T, typename U>
  struct getter_result {
    using type = std::conditional_t<std::is_lvalue_reference_v<T>, const U&, U>;
  };

  template <typename T, typename U>
  using getter_result_t = typename tools::getter_result<T, U>::type;
}


#line 12 "tools/cartesian_tree.hpp"

namespace tools {
  class cartesian_tree {
  public:
    struct vertex {
      int parent;
      int left;
      int right;
      std::pair<int, int> value_based_interval;
      std::pair<int, int> tree_based_interval;
    };

  private:
    std::vector<vertex> m_vertices;

  public:
    cartesian_tree() = default;
    template <std::ranges::random_access_range R, typename Compare = std::ranges::less>
    requires std::indirect_strict_weak_order<Compare, std::ranges::iterator_t<R>>
    explicit cartesian_tree(R&& a, const Compare comp = {}) : m_vertices(std::ranges::distance(a)) {
      if (this->size() == 0) return;

      static constexpr int NONE = -1;
      const auto begin = std::ranges::begin(a);

      for (int i = 0; i < this->size(); ++i) {
        this->m_vertices[i].parent = i ? i - 1 : NONE;
        this->m_vertices[i].left = NONE;
        this->m_vertices[i].right = NONE;
        auto c = NONE;
        while (this->m_vertices[i].parent != NONE && std::invoke(comp, begin[i], begin[this->m_vertices[i].parent])) {
          if (c != NONE) {
            this->m_vertices[c].parent = this->m_vertices[i].parent;
          }
          c = this->m_vertices[i].parent;

          const auto gp = this->m_vertices[this->m_vertices[i].parent].parent;
          this->m_vertices[this->m_vertices[i].parent].parent = i;
          this->m_vertices[i].parent = gp;
        }
      }

      auto root = NONE;
      for (int i = 0; i < this->size(); ++i) {
        const auto p = this->m_vertices[i].parent;
        if (p == NONE) {
          root = i;
        } else {
          if (p < i) {
            this->m_vertices[p].right = i;
          } else {
            this->m_vertices[p].left = i;
          }
        }
      }

      std::vector<int> strict_left(this->size());
      strict_left[root] = 0;
      this->m_vertices[root].value_based_interval = this->m_vertices[root].tree_based_interval = std::make_pair(0, this->size());
      std::stack<int> stack;
      stack.push(root);
      while (!stack.empty()) {
        const auto here = stack.top();
        stack.pop();
        const auto& v = this->m_vertices[here];
        if (v.right != NONE) {
          strict_left[v.right] = here + 1;
          this->m_vertices[v.right].value_based_interval = std::make_pair(
            std::invoke(comp, begin[here], begin[v.right]) ? strict_left[v.right] : this->m_vertices[here].value_based_interval.first,
            this->m_vertices[here].value_based_interval.second
          );
          this->m_vertices[v.right].tree_based_interval = std::make_pair(
            strict_left[v.right],
            this->m_vertices[here].tree_based_interval.second
          );
          stack.push(v.right);
        }
        if (v.left != NONE) {
          strict_left[v.left] = strict_left[here];
          this->m_vertices[v.left].value_based_interval = this->m_vertices[v.left].tree_based_interval = std::make_pair(strict_left[v.left], here);
          stack.push(v.left);
        }
      }
    }
    template <std::ranges::input_range R, typename Compare = std::ranges::less>
    requires (std::indirect_strict_weak_order<Compare, typename std::vector<std::ranges::range_value_t<R>>::iterator> && !std::ranges::random_access_range<R>)
    explicit cartesian_tree(R&& a, const Compare comp = {}) : cartesian_tree(std::forward<R>(a) | std::ranges::to<std::vector>(), comp) {
    }

    int size() const {
      return this->m_vertices.size();
    }
    auto get_vertex(this auto&& self, const int i) -> tools::getter_result_t<decltype(self), vertex> {
      assert(0 <= i && i < self.size());
      return std::forward_like<decltype(self)>(self.m_vertices[i]);
    }
    auto vertices(this auto&& self) -> tools::getter_result_t<decltype(self), std::vector<vertex>> {
      return std::forward_like<decltype(self)>(self.m_vertices);
    }
  };
}


#line 1 "tools/chmax.hpp"



#line 1 "tools/cmp_less.hpp"



#line 1 "tools/integral.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}


#line 5 "tools/integral.hpp"

namespace tools {
  template <typename T>
  concept integral = tools::is_integral_v<T>;
}


#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = tools::is_signed<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename tools::make_unsigned<T>::type;
}


#line 7 "tools/cmp_less.hpp"

namespace tools {
  template <tools::integral T, tools::integral U>
  constexpr bool cmp_less(const T t, const U u) noexcept {
    using UT = tools::make_unsigned_t<T>;
    using UU = tools::make_unsigned_t<U>;
    if constexpr (tools::is_signed_v<T> == tools::is_signed_v<U>) {
      return t < u;
    } else if constexpr (tools::is_signed_v<T>) {
      return t < 0 ? true : static_cast<UT>(t) < u;
    } else {
      return u < 0 ? false : t < static_cast<UU>(u);
    }
  }
}


#line 6 "tools/chmax.hpp"

namespace tools {
  template <typename M, typename N>
  bool chmax(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (tools::integral<M> && tools::integral<N>) {
      updated = tools::cmp_less(lhs, rhs);
    } else {
      updated = lhs < rhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 1 "tools/chmin.hpp"



#line 6 "tools/chmin.hpp"

namespace tools {
  template <typename M, typename N>
  bool chmin(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (tools::integral<M> && tools::integral<N>) {
      updated = tools::cmp_less(rhs, lhs);
    } else {
      updated = rhs < lhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 1 "tools/cumsum2d.hpp"



#include <algorithm>
#line 6 "tools/cumsum2d.hpp"
#include <concepts>
#line 1 "tools/commutative_group.hpp"



#line 1 "tools/commutative_monoid.hpp"



#line 1 "tools/monoid.hpp"



#line 5 "tools/monoid.hpp"

namespace tools {
  template <typename M>
  concept monoid = requires(typename M::T x, typename M::T y) {
    { M::op(x, y) } -> std::same_as<typename M::T>;
    { M::e() } -> std::same_as<typename M::T>;
  };
}


#line 5 "tools/commutative_monoid.hpp"

namespace tools {
  template <typename M>
  concept commutative_monoid = tools::monoid<M>;
}


#line 1 "tools/group.hpp"



#line 6 "tools/group.hpp"

namespace tools {
  template <typename G>
  concept group = tools::monoid<G> && requires(typename G::T x) {
    { G::inv(x) } -> std::same_as<typename G::T>;
  };
}


#line 6 "tools/commutative_group.hpp"

namespace tools {
  template <typename G>
  concept commutative_group = tools::group<G> && tools::commutative_monoid<G>;
}


#line 1 "tools/groups.hpp"



#include <cstddef>
#line 1 "tools/arithmetic.hpp"



#line 6 "tools/arithmetic.hpp"

namespace tools {
  template <typename T>
  concept arithmetic = tools::integral<T> || std::floating_point<T>;
}


#line 7 "tools/groups.hpp"

namespace tools {
  namespace groups {
    template <typename G>
    struct bit_xor {
      using T = G;
      static T op(const T& x, const T& y) {
        return x ^ y;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& x) {
        return x;
      }
    };

    template <typename G>
    struct multiplies {
      using T = G;
      static T op(const T& x, const T& y) {
        return x * y;
      }
      static T e() {
        return T(1);
      }
      static T inv(const T& x) {
        return e() / x;
      }
    };

    template <typename G>
    struct plus {
      using T = G;
      static T op(const T& x, const T& y) {
        return x + y;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& x) {
        return -x;
      }
    };
  }
}


#line 14 "tools/cumsum2d.hpp"

namespace tools {

  template <typename X>
  class cumsum2d {
    using G = std::conditional_t<tools::commutative_group<X>, X, tools::groups::plus<X>>;
    using T = typename G::T;
    int m_height;
    int m_width;
    std::vector<T> m_preprocessed;

    int p(const int y, const int x) const {
      return y * (this->m_width + 1) + x;
    }

  public:
    template <std::ranges::input_range R>
    requires std::ranges::input_range<std::ranges::range_reference_t<R>>
          && std::assignable_from<T&, std::ranges::range_value_t<std::ranges::range_reference_t<R>>>
    explicit cumsum2d(R&& range) : m_height(0), m_width(0) {
      for (auto&& row : std::forward<R>(range)) {
        this->m_preprocessed.push_back(G::e());
        const auto old_size = this->m_preprocessed.size();
        std::ranges::copy(std::forward<decltype(row)>(row), std::back_inserter(this->m_preprocessed));
        if (this->m_height == 0) {
          this->m_width = this->m_preprocessed.size() - old_size;
          this->m_preprocessed.insert(this->m_preprocessed.begin(), this->m_width + 1, G::e());
        } else {
          assert(std::cmp_equal(this->m_width, this->m_preprocessed.size() - old_size));
        }
        ++this->m_height;
      }

      for (int y = 0; y < this->m_height; ++y) {
        for (int x = 0; x < this->m_width; ++x) {
          this->m_preprocessed[this->p(y + 1, x + 1)] = G::op(this->m_preprocessed[this->p(y + 1, x)], this->m_preprocessed[this->p(y + 1, x + 1)]);
        }
      }
      for (int x = 0; x < this->m_width; ++x) {
        for (int y = 0; y < this->m_height; ++y) {
          this->m_preprocessed[this->p(y + 1, x + 1)] = G::op(this->m_preprocessed[this->p(y, x + 1)], this->m_preprocessed[this->p(y + 1, x + 1)]);
        }
      }
    }

    T query(const int y1, const int y2, const int x1, const int x2) const {
      assert(y1 <= y2 && y2 <= this->m_height);
      assert(x1 <= x2 && x2 <= this->m_width);
      return G::op(
        G::op(
          G::op(
            this->m_preprocessed[this->p(y2, x2)],
            G::inv(this->m_preprocessed[this->p(y2, x1)])
          ),
          G::inv(this->m_preprocessed[this->p(y1, x2)])
        ),
        this->m_preprocessed[this->p(y1, x1)]
      );
    }
  };
}


#line 12 "tests/cartesian_tree/value_based_interval.test.cpp"

using ll = long long;

ll solve(const int N, const int M, const std::vector<std::vector<int>>& A) {
  const tools::cumsum2d<int> sum(A);

  auto answer = std::numeric_limits<ll>::min();
  for (int r1 = 0; r1 < N; ++r1) {
    std::vector<int> row(M, std::numeric_limits<int>::max());
    for (int r2 = r1 + 1; r2 <= N; ++r2) {
      for (int c = 0; c < M; ++c) {
        tools::chmin(row[c], A[r2 - 1][c]);
      }
      const tools::cartesian_tree cartesian_tree(row);
      for (int c = 0; c < M; ++c) {
        const auto& [c1, c2] = cartesian_tree.get_vertex(c).value_based_interval;
        tools::chmax(answer, static_cast<ll>(row[c]) * sum.query(r1, r2, c1, c2));
      }
    }
  }

  return answer;
}

void sample01() {
  const int N = 3;
  const int M = 3;
  const std::vector<std::vector<int>> A = {
    {5, 4, 3},
    {4, 3, 2},
    {3, 2, 1},
  };
  assert_that(solve(N, M, A) == 48);
}

void sample02() {
  const int N = 4;
  const int M = 5;
  const std::vector<std::vector<int>> A = {
    {3, 1, 4, 1, 5},
    {9, 2, 6, 5, 3},
    {5, 8, 9, 7, 9},
    {3, 2, 3, 8, 4},
  };
  assert_that(solve(N, M, A) == 231);
}

void sample03() {
  const int N = 6;
  const int M = 6;
  const std::vector<std::vector<int>> A = {
    {1, 300, 300, 300, 300, 300},
    {300, 1, 300, 300, 300, 300},
    {300, 300, 1, 300, 300, 300},
    {300, 300, 300, 1, 300, 300},
    {300, 300, 300, 300, 1, 300},
    {300, 300, 300, 300, 300, 1},
  };
  assert_that(solve(N, M, A) == 810000);
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  sample01();
  sample02();
  sample03();

  return 0;
}
Back to top page