結果
| 問題 | No.1435 Mmm...... |
| ユーザー |
 cutmdo
|
| 提出日時 | 2025-01-23 03:59:24 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 311 ms / 2,000 ms |
| コード長 | 5,740 bytes |
| コンパイル時間 | 1,401 ms |
| コンパイル使用メモリ | 126,196 KB |
| 実行使用メモリ | 17,200 KB |
| 最終ジャッジ日時 | 2025-01-23 03:59:31 |
| 合計ジャッジ時間 | 7,056 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 24 |
ソースコード
#define PROBLEM "https://yukicoder.me/problems/no/1435"#include <algorithm>#include <iostream>#include <ranges>#include <vector>#include <iostream>#include <deque>#include <utility>#include <vector>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> conceptis_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 { _l = std::max(_l, 0); _r = std::min(_r, m_size - 1); auto l = _l + m_size; auto r = _r + 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 { returnm_node[0].m_val; } /* * f([l, r]) = true となる最大のr * judge: (Monoid) -> bool **/ template <class F> constexpr automax_right(int _l, const F& judge) const { if (!judge(Monoid())) { throw std::runtime_error("SegmentTree.max_right.judge(e) must betrue"); } 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; } 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 l : std::views::iota(0, n)) {auto r = segtree.max_right(l, [](const M& m) {auto [min1, min2, max] = m.m_val;return max <= min1 + min2;});r = std::min(r, n - 1);ans += r - l;}std::cout << ans << std::endl;}