proconlib
This documentation is automatically generated by competitive-verifier/competitive-verifier
tests/cartesian_tree/interval.test.cpp
- View this file on GitHub
- Last update: 2025-01-25 08:45:50+09:00
- Problem: https://atcoder.jp/contests/abc311/tasks/abc311_g
Depends on
Cartesian tree (tools/cartesian_tree.hpp)- chmax function (tools/chmax.hpp)
- chmin function (tools/chmin.hpp)
- 2D cumulative sum (tools/cumsum2d.hpp)
- Typical groups (tools/group.hpp)
- Check whether T is a group (tools/is_group.hpp)
Code
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc311/tasks/abc311_g
// competitive-verifier: IGNORE
#include <iostream>
#include <vector>
#include <limits>
#include <functional>
#include "tools/cumsum2d.hpp"
#include "tools/chmin.hpp"
#include "tools/cartesian_tree.hpp"
#include "tools/chmax.hpp"
using ll = long long;
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
int N, M;
std::cin >> N >> M;
auto A = std::vector(N, std::vector<int>(M));
for (auto& A_r : A) {
for (auto& A_rc: A_r) {
std::cin >> A_rc;
}
}
const tools::cumsum2d<int> sum(A);
ll 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<int> cartesian_tree(row);
for (int c = 0; c < M; ++c) {
const auto& [c1, c2] = cartesian_tree.get_vertex(c).interval;
tools::chmax(answer, static_cast<ll>(row[c]) * sum.query(r1, r2, c1, c2));
}
}
}
std::cout << answer << '\n';
return 0;
}
#line 1 "tests/cartesian_tree/interval.test.cpp"
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc311/tasks/abc311_g
// competitive-verifier: IGNORE
#include <iostream>
#include <vector>
#include <limits>
#include <functional>
#line 1 "tools/cumsum2d.hpp"
#include <type_traits>
#include <cstddef>
#line 7 "tools/cumsum2d.hpp"
#include <iterator>
#include <algorithm>
#include <cassert>
#line 1 "tools/is_group.hpp"
#line 5 "tools/is_group.hpp"
#include <utility>
namespace tools {
template <typename G, typename = void>
struct is_group : ::std::false_type {};
template <typename G>
struct is_group<G, ::std::enable_if_t<
::std::is_same_v<typename G::T, decltype(G::op(::std::declval<typename G::T>(), ::std::declval<typename G::T>()))> &&
::std::is_same_v<typename G::T, decltype(G::e())> &&
::std::is_same_v<typename G::T, decltype(G::inv(::std::declval<typename G::T>()))>
, void>> : ::std::true_type {};
template <typename G>
inline constexpr bool is_group_v = ::tools::is_group<G>::value;
}
#line 1 "tools/group.hpp"
namespace tools {
namespace group {
template <typename G>
struct plus {
using T = G;
static T op(const T& lhs, const T& rhs) {
return lhs + rhs;
}
static T e() {
return T(0);
}
static T inv(const T& v) {
return -v;
}
};
template <typename G>
struct multiplies {
using T = G;
static T op(const T& lhs, const T& rhs) {
return lhs * rhs;
}
static T e() {
return T(1);
}
static T inv(const T& v) {
return e() / v;
}
};
template <typename G>
struct bit_xor {
using T = G;
static T op(const T& lhs, const T& rhs) {
return lhs ^ rhs;
}
static T e() {
return T(0);
}
static T inv(const T& v) {
return v;
}
};
}
}
#line 12 "tools/cumsum2d.hpp"
namespace tools {
template <typename X>
class cumsum2d {
private:
using G = ::std::conditional_t<::tools::is_group_v<X>, X, tools::group::plus<X>>;
using T = typename G::T;
::std::size_t height;
::std::size_t width;
::std::vector<T> preprocessed;
public:
template <typename Range>
explicit cumsum2d(const Range& range) {
const auto begin = ::std::begin(range);
const auto end = ::std::end(range);
this->height = ::std::distance(begin, end);
this->width = this->height == 0 ? 0 : ::std::distance(::std::begin(*begin), ::std::end(*begin));
this->preprocessed.reserve((this->height + 1) * (this->width + 1));
::std::fill_n(::std::back_inserter(this->preprocessed), (this->height + 1) * (this->width + 1), G::e());
{
auto it1 = begin;
for (::std::size_t y = 0; y < this->height; ++y, ++it1) {
auto it2 = ::std::begin(*it1);
for (::std::size_t x = 0; x < this->width; ++x, ++it2) {
this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)] = G::op(this->preprocessed[(y + 1) * (this->width + 1) + x], *it2);
}
}
}
for (::std::size_t x = 0; x < this->width; ++x) {
for (::std::size_t y = 0; y < this->height; ++y) {
this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)] = G::op(this->preprocessed[y * (this->width + 1) + (x + 1)], this->preprocessed[(y + 1) * (this->width + 1) + (x + 1)]);
}
}
}
T query(const ::std::size_t y1, const ::std::size_t y2, const ::std::size_t x1, const ::std::size_t x2) const {
assert(y1 <= y2 && y2 <= this->height);
assert(x1 <= x2 && x2 <= this->width);
return G::op(
G::op(
G::op(
this->preprocessed[y2 * (this->width + 1) + x2],
G::inv(this->preprocessed[y2 * (this->width + 1) + x1])
),
G::inv(this->preprocessed[y1 * (this->width + 1) + x2])
),
this->preprocessed[y1 * (this->width + 1) + x1]
);
}
};
}
#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 (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
updated = ::std::cmp_less(rhs, lhs);
} else {
updated = rhs < lhs;
}
if (updated) lhs = rhs;
return updated;
}
}
#line 1 "tools/cartesian_tree.hpp"
#line 9 "tools/cartesian_tree.hpp"
#include <stack>
#line 11 "tools/cartesian_tree.hpp"
namespace tools {
template <typename T, typename Compare = ::std::less<T>>
class cartesian_tree {
public:
struct vertex {
::std::size_t parent;
::std::size_t left;
::std::size_t right;
::std::pair<::std::size_t, ::std::size_t> interval;
};
private:
Compare m_comp;
::std::vector<vertex> m_vertices;
public:
cartesian_tree() = default;
cartesian_tree(const ::tools::cartesian_tree<T, Compare>&) = default;
cartesian_tree(::tools::cartesian_tree<T, Compare>&&) = default;
~cartesian_tree() = default;
::tools::cartesian_tree<T, Compare>& operator=(const ::tools::cartesian_tree<T, Compare>&) = default;
::tools::cartesian_tree<T, Compare>& operator=(::tools::cartesian_tree<T, Compare>&&) = default;
explicit cartesian_tree(const ::std::vector<T>& a, const Compare& comp = Compare()) : m_comp(comp), m_vertices(a.size()) {
const auto NONE = ::std::numeric_limits<::std::size_t>::max();
for (::std::size_t i = 0; i < a.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 && this->m_comp(a[i], a[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 (::std::size_t i = 0; i < a.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<::std::size_t> strict_left(a.size());
strict_left[root] = 0;
this->m_vertices[root].interval = ::std::make_pair(0, a.size());
::std::stack<::std::size_t> 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].interval = ::std::make_pair(
this->m_comp(a[here], a[v.right]) ? strict_left[v.right] : this->m_vertices[here].interval.first,
this->m_vertices[here].interval.second
);
stack.push(v.right);
}
if (v.left != NONE) {
strict_left[v.left] = strict_left[here];
this->m_vertices[v.left].interval = ::std::make_pair(strict_left[v.left], here);
stack.push(v.left);
}
}
}
template <typename InputIterator>
cartesian_tree(const InputIterator begin, const InputIterator end, const Compare& comp = Compare()) : cartesian_tree(::std::vector<T>(begin, end), comp) {
}
::std::size_t size() const {
return this->m_vertices.size();
}
const vertex& get_vertex(::std::size_t i) const {
assert(i < this->size());
return this->m_vertices[i];
}
const ::std::vector<vertex>& vertices() const {
return this->m_vertices;
}
};
}
#line 1 "tools/chmax.hpp"
#line 6 "tools/chmax.hpp"
namespace tools {
template <typename M, typename N>
bool chmax(M& lhs, const N& rhs) {
bool updated;
if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
updated = ::std::cmp_less(lhs, rhs);
} else {
updated = lhs < rhs;
}
if (updated) lhs = rhs;
return updated;
}
}
#line 12 "tests/cartesian_tree/interval.test.cpp"
using ll = long long;
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
int N, M;
std::cin >> N >> M;
auto A = std::vector(N, std::vector<int>(M));
for (auto& A_r : A) {
for (auto& A_rc: A_r) {
std::cin >> A_rc;
}
}
const tools::cumsum2d<int> sum(A);
ll 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<int> cartesian_tree(row);
for (int c = 0; c < M; ++c) {
const auto& [c1, c2] = cartesian_tree.get_vertex(c).interval;
tools::chmax(answer, static_cast<ll>(row[c]) * sum.query(r1, r2, c1, c2));
}
}
}
std::cout << answer << '\n';
return 0;
}