結果

問題 No.1435 Mmm......
ユーザー cutmdo
提出日時 2025-01-23 04:46:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 6,770 bytes
コンパイル時間 1,345 ms
コンパイル使用メモリ 124,116 KB
実行使用メモリ 17,272 KB
最終ジャッジ日時 2025-01-23 04:46:46
合計ジャッジ時間 5,982 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/1435"

#include <algorithm>
#include <iostream>
#include <ranges>
#include <vector>

#include <iostream>
#include <utility>
#include <vector>
#include <deque>
namespace mtd {  template <class S,                S element,              class op                >  requires std::is_invocable_r_v<S, op, S, S>  struct Monoid {    using value_type = S;    constexpr static S _element = element;    using op_type = op;    S m_val;    constexpr Monoid(S val) : m_val(val) {}    constexpr Monoid() : Monoid(element) {}    constexpr Monoid binaryOperation(const Monoid& m2) const {      return op()(m_val, m2.m_val);    }    friend std::ostream& operator<<(std::ostream& os,                                    const Monoid<S, element, op>& m) {      return os << m.m_val;    }  };  namespace __detail {    template <typename T, template <typename, auto, typename> typename S>    concept is_monoid_specialization_of = requires {      typename std::enable_if_t<std::is_same_v<          T, S<typename T::value_type, T::_element, typename T::op_type>>>;    };  }    template <typename M>  concept monoid = __detail::is_monoid_specialization_of<M, Monoid>;}  
namespace mtd {  template <monoid Monoid>  class SegmentTree {  private:    const int m_size;    std::vector<Monoid> m_node;    using S = decltype(Monoid().m_val);    constexpr int calcSize(int n) const {      int size = 1;      while (size < n) { size <<= 1; }      return size;    }    template <class Lambda>    constexpr auto _update_op(int itr, Monoid&& val, const Lambda& op) {      int i = itr + m_size - 1;      m_node[i] = op(m_node[i], std::forward<decltype(val)>(val));      while (i) {        i = (i - 1) >> 1;        m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]);      }    }    constexpr auto _query(int _l, int _r) const {      auto l = std::max(_l, 0) + m_size;      auto r = std::min(_r, m_size - 1) + m_size;      auto lm = Monoid();      auto rm = Monoid();      while (l <= r) {        if (l & 1) {          lm = lm.binaryOperation(m_node[l - 1]);          ++l;        }        if (!(r & 1)) {          rm = m_node[r - 1].binaryOperation(rm);          --r;        }        l >>= 1, r >>= 1;      }      return lm.binaryOperation(rm);    }    constexpr auto _construct(const std::vector<S>& vec) {      for (unsigned int i = 0; i < vec.size(); ++i) {        m_node[i + m_size - 1] = Monoid(vec[i]);      }      for (int i = m_size - 2; i >= 0; --i) {        m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]);      }    }  public:    SegmentTree(int n) : m_size(calcSize(n)), m_node((m_size << 1) - 1) {}    SegmentTree(int n, const std::vector<S>& vec) : SegmentTree(n) {      _construct(vec);    }    template <class Lambda>    constexpr auto update_op(int itr, Monoid&& val, const Lambda& op) {      return _update_op(itr, std::forward<Monoid>(val), op);    }    constexpr auto update(int itr, Monoid&& val) {      return update_op(itr, std::forward<Monoid>(val),                       [](const Monoid&, const Monoid& m2) { return m2; });    }    constexpr auto add(int itr, Monoid&& val) {      return update_op(itr, std::forward<Monoid>(val),                       [](const Monoid& m1, const Monoid& m2) {                         return Monoid(m1.m_val + m2.m_val);                       });    }    constexpr auto query(int l, int r) const { return _query(l, r).m_val; }    constexpr auto query_all() const { return m_node[0].m_val; }    /*     * f([l, r]) = true となる最大のr     * judge: (Monoid) -> bool     **/    template <class F>    constexpr auto max_right(int _l, const F& judge) const {      if (!judge(Monoid())) {        throw std::runtime_error("SegmentTree.max_right.judge(e) must be true");      }      auto l = std::max(_l, 0) + m_size;      auto r = 2 * m_size - 1;      auto lm = Monoid();      while (l <= r) {        if (l & 1) {          auto next = lm.binaryOperation(m_node[l - 1]);          if (!judge(next)) {            auto itr = l;            while (itr < m_size) {              auto litr = 2 * itr;              auto ritr = 2 * itr + 1;              auto lval = lm.binaryOperation(m_node[litr - 1]);              if (!judge(lval)) {                itr = litr;              } else {                itr = ritr;                std::swap(lm, lval);              }            }            return itr - m_size - 1;          }          std::swap(lm, next);          ++l;        }        l >>= 1, r >>= 1;      }      return m_size - 1;    }    /*     * f([l, r]) = true となる最小のl     * judge: (Monoid) -> bool     **/    template <class F>    constexpr auto min_left(int _r, const F& judge) const {      if (!judge(Monoid())) {        throw std::runtime_error("SegmentTree.min_left.judge(e) must be true");      }      auto l = m_size;      auto r = std::min(_r, m_size - 1) + m_size;      auto rm = Monoid();      while (l <= r) {        if (l & 1) { ++l; }        if (!(r & 1) || (_r == m_size - 1 && r == 1)) {          auto next = m_node[r - 1].binaryOperation(rm);          if (!judge(next)) {            auto itr = r;            while (itr < m_size) {              auto litr = 2 * itr;              auto ritr = 2 * itr + 1;              auto rval = m_node[ritr - 1].binaryOperation(rm);              if (!judge(rval)) {                itr = ritr;              } else {                itr = litr;                std::swap(rm, rval);              }            }            return itr - m_size + 1;          }          std::swap(rm, next);          --r;        }        l >>= 1, r >>= 1;      }      return 0;    }    constexpr auto debug() const {      for (int i = 0; i < m_size; ++i) {        std::cout << m_node[m_size + i - 1] << " ";      }      std::cout << std::endl;    }  };}  

using ll = long long;

struct T {
  ll min1, min2, max;
  constexpr T(ll _min1, ll _min2, ll _max)
      : min1(_min1), min2(_min2), max(_max) {}
};
auto op = [](const T& a, const T& b) {
  std::vector<ll> v{a.min1, a.min2, b.min1, b.min2};
  std::ranges::sort(v);
  return T(v[0], v[1], std::max(a.max, b.max));
};
constexpr T e{1LL << 60, 1LL << 60, -(1LL << 60)};
using M = mtd::Monoid<T, e, decltype(op)>;

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  int n;
  std::cin >> n;
  std::vector<ll> a(n);
  for (auto i : std::views::iota(0, n)) { std::cin >> a[i]; }

  auto segtree = mtd::SegmentTree<M>(n);
  for (auto i : std::views::iota(0, n)) {
    segtree.update(i, T(a[i], 1LL << 60, a[i]));
  }

  ll ans = 0;
  for (auto r : std::views::iota(0, n)) {
    auto l = segtree.min_left(r, [](const M& m) {
      auto [min1, min2, max] = m.m_val;
      return max <= min1 + min2;
    });
    ans += r - l;
  }
  std::cout << ans << std::endl;
}
0