tests/largest_rectangle_in_histogram.test.cpp

• View this file on GitHub
• Last update: 2025-01-25 08:45:50+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_C

Depends on

• chmax function (tools/chmax.hpp)
• Largest rectangle in histogram (tools/largest_rectangle_in_histogram.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_C

#include <iostream>
#include <vector>
#include "tools/largest_rectangle_in_histogram.hpp"

using ll = long long;

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

  ll N;
  std::cin >> N;
  std::vector<ll> h(N);
  for (ll& h_i : h) std::cin >> h_i;
  std::cout << tools::largest_rectangle_in_histogram(h.begin(), h.end()) << '\n';

  return 0;
}

#line 1 "tests/largest_rectangle_in_histogram.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DPL_3_C

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



#include <iterator>
#include <stack>
#include <utility>
#include <tuple>
#line 1 "tools/chmax.hpp"



#include <type_traits>
#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 9 "tools/largest_rectangle_in_histogram.hpp"

namespace tools {
  template <typename InputIterator>
  typename ::std::iterator_traits<InputIterator>::value_type largest_rectangle_in_histogram(const InputIterator& begin, const InputIterator& end) {
    using T = typename ::std::iterator_traits<InputIterator>::value_type;

    T result = 0;
    ::std::stack<::std::pair<T, T>> dp;
    for (auto [i, it, breaks] = ::std::make_tuple(0, begin, false); !breaks; ++i, breaks = it == end, it = ::std::next(it, breaks ? 0 : 1)) {
      const T v = it != end ? *it : 0;
      if (dp.empty() || dp.top().second < v) {
        dp.emplace(i, v);
      } else if (dp.top().second > v) {
        T leftmost;
        while (!dp.empty() && dp.top().second > v) {
          leftmost = dp.top().first;
          ::tools::chmax(result, dp.top().second * (i - dp.top().first));
          dp.pop();
        }
        if (dp.empty() || dp.top().second < v) {
          dp.emplace(leftmost, v);
        }
      }
    }

    return result;
  }
}


#line 6 "tests/largest_rectangle_in_histogram.test.cpp"

using ll = long long;

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

  ll N;
  std::cin >> N;
  std::vector<ll> h(N);
  for (ll& h_i : h) std::cin >> h_i;
  std::cout << tools::largest_rectangle_in_histogram(h.begin(), h.end()) << '\n';

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	5 ms	4 MB
g++	00_sample_01.in	AC	4 ms	3 MB
g++	01_small_00.in	AC	4 ms	4 MB
g++	01_small_01.in	AC	4 ms	4 MB
g++	02_corner_00.in	AC	4 ms	4 MB
g++	02_corner_01.in	AC	4 ms	4 MB
g++	02_corner_02.in	AC	4 ms	3 MB
g++	02_corner_03.in	AC	4 ms	3 MB
g++	02_corner_04.in	AC	4 ms	4 MB
g++	02_corner_05.in	AC	4 ms	4 MB
g++	03_wide_00.in	AC	4 ms	4 MB
g++	03_wide_01.in	AC	4 ms	4 MB
g++	03_wide_02.in	AC	4 ms	4 MB
g++	04_tall_00.in	AC	4 ms	3 MB
g++	04_tall_01.in	AC	4 ms	4 MB
g++	04_tall_02.in	AC	4 ms	4 MB
g++	05_rand_00.in	AC	4 ms	4 MB
g++	05_rand_01.in	AC	4 ms	4 MB
g++	05_rand_02.in	AC	4 ms	4 MB
g++	05_rand_03.in	AC	4 ms	4 MB
g++	05_rand_04.in	AC	4 ms	4 MB
g++	05_rand_05.in	AC	4 ms	4 MB
g++	05_rand_06.in	AC	4 ms	4 MB
g++	05_rand_07.in	AC	4 ms	3 MB
g++	06_ordered_00.in	AC	10 ms	6 MB
g++	06_ordered_01.in	AC	9 ms	4 MB
g++	07_unique_00.in	AC	9 ms	4 MB
g++	07_unique_01.in	AC	9 ms	4 MB
g++	08_large_00.in	AC	10 ms	4 MB
g++	08_large_01.in	AC	11 ms	4 MB
g++	08_large_02.in	AC	11 ms	4 MB
g++	08_large_03.in	AC	11 ms	4 MB
g++	08_large_04.in	AC	11 ms	4 MB
g++	08_large_05.in	AC	11 ms	4 MB
g++	09_corner_00.in	AC	10 ms	4 MB
g++	09_corner_01.in	AC	10 ms	4 MB

Back to top page