#include #include #include #include #include #include #include #include #include namespace ranges = std::ranges; namespace views = std::views; // #include "Src/Number/IntegerDivision.hpp" // #include "Src/Utility/BinarySearch.hpp" #include #include namespace zawa { using i16 = std::int16_t; using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u8 = std::uint8_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using usize = std::size_t; } // namespace zawa #include #include namespace zawa { template class CompressedSequence { public: static constexpr u32 NotFound = std::numeric_limits::max(); CompressedSequence() = default; template CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} { std::sort(comped_.begin(), comped_.end()); comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end()); comped_.shrink_to_fit(); f_.reserve(std::distance(first, last)); for (auto it{first} ; it != last ; it++) { f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it))); } } CompressedSequence(const std::vector& A) : CompressedSequence(A.begin(), A.end()) {} inline usize size() const noexcept { return comped_.size(); } u32 operator[](const T& v) const { return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v)); } u32 upper_bound(const T& v) const { return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v)); } u32 find(const T& v) const { u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v)); return i == comped_.size() or comped_[i] != v ? NotFound : i; } bool contains(const T& v) const { u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v)); return i < comped_.size() and comped_[i] == v; } u32 at(const T& v) const { u32 res = find(v); assert(res != NotFound); return res; } inline u32 map(u32 i) const noexcept { assert(i < f_.size()); return f_[i]; } inline T inverse(u32 i) const noexcept { assert(i < size()); return comped_[i]; } inline std::vector comped() const noexcept { return comped_; } private: std::vector comped_; std::vector f_; }; } // namespace zawa // #include "Src/Sequence/RunLengthEncoding.hpp" // #include "Src/Algebra/Group/AdditiveGroup.hpp" // #include "Src/DataStructure/FenwickTree/FenwickTree.hpp" // #include "Src/DataStructure/SegmentTree/SegmentTree.hpp" // #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp" #include namespace zawa { namespace concepts { template concept Semigroup = requires { typename T::Element; { T::operation(std::declval(), std::declval()) } -> std::same_as; }; } // namespace concepts } // namespace zawa namespace zawa { namespace concepts { template concept Identitiable = requires { typename T::Element; { T::identity() } -> std::same_as; }; template concept Monoid = Semigroup and Identitiable; } // namespace } // namespace zawa namespace zawa { namespace concepts { template concept MonoidWithAction = requires { requires Monoid; requires Monoid; { T::mapping( std::declval(), std::declval() ) } -> std::same_as; }; } // namespace concepts } // namespace zawa #include namespace zawa { template class LazySegmentTree { public: using VM = S::ValueMonoid; using V = typename VM::Element; using OM = S::OperatorMonoid; using O = typename OM::Element; LazySegmentTree() = default; explicit LazySegmentTree(usize n) : m_n{n}, m_sz{1u << (std::bit_width(n))}, m_dat(m_sz << 1, VM::identity()), m_lazy(m_sz << 1, OM::identity()) {} explicit LazySegmentTree(const std::vector& a) : m_n{a.size()}, m_sz{1u << (std::bit_width(a.size()))}, m_dat(m_sz << 1, VM::identity()), m_lazy(m_sz << 1, OM::identity()) { std::ranges::copy(a, m_dat.begin() + inner_size()); for (usize i = inner_size() ; --i ; ) recalc(i); } [[nodiscard]] inline usize size() const noexcept { return m_n; } [[nodiscard]] V operator[](usize i) { assert(i < size()); return get(i, 1, 0, inner_size()); } [[nodiscard]] V get(usize i) { return (*this)[i]; } [[nodiscard]] V product(usize l, usize r) { assert(l <= r and r <= size()); return product(l, r, 1, 0, inner_size()); } void operation(usize l, usize r, const O& o) { assert(l <= r and r <= size()); return operation(l, r, o, 1, 0, inner_size()); } void assign(usize i, const V& v) { assert(i < size()); assign(i, v, 1, 0, inner_size()); } void operation(usize i, const O& o) { assert(i < size()); operation(i, o, 1, 0, inner_size()); } private: using NodeInfo = std::tuple; public: template requires std::predicate usize maxRight(usize l, F f) { assert(l <= size()); if (!f(VM::identity())) return l; if (l == size()) return size(); std::vector ranges; partition_range(l, size(), ranges, 1, 0, inner_size()); V prod = VM::identity(); for (auto [nd, nl, nr] : ranges) { if (!f(VM::operation(prod, m_dat[nd]))) { return maxRight(f, prod, nd, nl, nr); } else { prod = VM::operation(prod, m_dat[nd]); } } return size(); } template requires std::predicate usize minLeft(usize r, F f) { assert(r <= size()); if (!f(VM::identity())) return r; if (!r) return 0; std::vector ranges; partition_range(0, r, ranges, 1, 0, inner_size()); V prod = VM::identity(); for (auto [nd, nl, nr] : ranges | std::views::reverse) { if (!f(VM::operation(m_dat[nd], prod))) { return minLeft(f, prod, nd, nl, nr); } else { prod = VM::operation(prod, m_dat[nd]); } } return 0; } private: usize m_n{}, m_sz{}; std::vector m_dat; std::vector m_lazy; inline usize inner_size() const noexcept { return m_sz; } void recalc(usize nd) { // assert(nd < inner_size()); m_dat[nd] = VM::operation(m_dat[nd << 1 | 0], m_dat[nd << 1 | 1]); } void propagate(usize nd) { // assert(nd < inner_size()); for (usize ch : {nd << 1 | 0, nd << 1 | 1}) { m_dat[ch] = S::mapping(m_dat[ch], m_lazy[nd]); m_lazy[ch] = OM::operation(m_lazy[ch], m_lazy[nd]); } m_lazy[nd] = OM::identity(); } V product(usize ql, usize qr, usize nd, usize nl, usize nr) { if (qr <= nl or nr <= ql) return VM::identity(); if (ql <= nl and nr <= qr) return m_dat[nd]; propagate(nd); const usize m = (nl + nr) >> 1; return VM::operation( product(ql, qr, nd << 1 | 0, nl, m), product(ql, qr, nd << 1 | 1, m, nr) ); } V get(usize i, usize nd, usize nl, usize nr) { if (nd >= inner_size()) return m_dat[nd]; propagate(nd); const usize m = (nl + nr) >> 1; return i < m ? get(i, nd << 1 | 0, nl, m) : get(i, nd << 1 | 1, m, nr); } void operation(usize ql, usize qr, const O& o, usize nd, usize nl, usize nr) { if (qr <= nl or nr <= ql) return; if (ql <= nl and nr <= qr) { m_dat[nd] = S::mapping(m_dat[nd], o); m_lazy[nd] = OM::operation(m_lazy[nd], o); return; } propagate(nd); const usize m = (nl + nr) >> 1; operation(ql, qr, o, nd << 1 | 0, nl, m); operation(ql, qr, o, nd << 1 | 1, m, nr); recalc(nd); } void operation(usize i, const O& o, usize nd, usize nl, usize nr) { if (nl == i and i + 1 == nr) { m_dat[nd] = S::mapping(m_dat[nd], o); // 葉頂点なので、lazyへのopは不要 return; } propagate(nd); const usize m = (nl + nr) >> 1; i < m ? operation(i, o, nd << 1 | 0, nl, m) : operation(i, o, nd << 1 | 1, m, nr); recalc(nd); } void assign(usize i, const V& v, usize nd, usize nl, usize nr) { if (nl == i and i + 1 == nr) { m_dat[nd] = v; return; } propagate(nd); const usize m = (nl + nr) >> 1; i < m ? assign(i, v, nd << 1 | 0, nl, m) : assign(i, v, nd << 1 | 1, m, nr); recalc(nd); } void partition_range(usize ql, usize qr, std::vector& res, usize nd, usize nl, usize nr) { if (qr <= nl or nr <= ql) return; if (ql <= nl and nr <= qr) { res.emplace_back(nd, nl, nr); return; } propagate(nd); const usize m = (nl + nr) >> 1; partition_range(ql, qr, res, nd << 1 | 0, nl, m); partition_range(ql, qr, res, nd << 1 | 1, m, nr); } template requires std::predicate usize maxRight(F f, const V& prod, usize nd, usize nl, usize nr) { if (nd >= inner_size()) return nl; propagate(nd); const usize m = (nl + nr) >> 1, lch = nd << 1 | 0, rch = nd << 1 | 1; return f(VM::operation(prod, m_dat[lch])) ? maxRight(f, VM::operation(prod, m_dat[lch]), rch, m, nr) : maxRight(f, prod, lch, nl, m); } template requires std::predicate usize minLeft(F f, const V& prod, usize nd, usize nl, usize nr) { if (nd >= inner_size()) return nr; propagate(nd); const usize m = (nl + nr) >> 1, lch = nd << 1 | 0, rch = nd << 1 | 1; return f(VM::operation(m_dat[rch], prod)) ? minLeft(f, VM::operation(m_dat[rch], prod), lch, nl, m) : minLeft(f, prod, rch, m, nr); } }; } // namespace zawa using namespace zawa; // #include "atcoder/modint" // using mint = atcoder::modint998244353; using namespace std; #include struct VM { using Element = optional; static Element identity() { return nullopt; } static Element operation(Element L, Element R) { if (!L) return R; if (!R) return L; return max(L.value(), R.value()); } }; struct OM { using Element = long long; static Element identity() { return 0LL; } static Element operation(Element L, Element R) { return L + R; } }; struct ACT { using ValueMonoid = VM; using OperatorMonoid = OM; static VM::Element mapping(VM::Element v, OM::Element o) { if (!v) return o ? VM::Element{o} : nullopt; else return v.value() + o; } }; int N, A, X[200020], Y[200020], V[200020]; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> N >> A; A *= 2; for (int i = 0 ; i < N ; i++) { cin >> X[i] >> Y[i] >> V[i]; X[i] *= 2; Y[i] *= 2; } CompressedSequence xs(vector(X, X + N)), ys(vector(Y, Y + N)); vector> event(xs.size()); for (int i = 0 ; i < N ; i++) event[xs.map(i)].push_back(i); LazySegmentTree seg(ys.size()); auto insert = [&](long long y, int v) -> void { seg.operation(ys[y - A - 1], ys.at(y) + 1, v); }; auto erase = [&](long long y, int v) -> void { seg.operation(ys[y - A - 1], ys.at(y) + 1, -v); }; auto eval = [&]() -> long long { auto prod = seg.product(0, seg.size()); return prod ? prod.value() : 0LL; }; int j = 0; long long ans = 0LL; for (int i = 0 ; i < ssize(event) ; i++) { const int x = xs.inverse(i); while (xs.inverse(j) + A < x) { for (int k : event[j]) erase(Y[k], V[k]); ans = max(ans, eval()); j++; } for (int k : event[i]) insert(Y[k], V[k]); ans = max(ans, eval()); } for ( ; j < ssize(event) ; j++) { for (int k : event[j]) erase(Y[k], V[k]); ans = max(ans, eval()); j++; } cout << ans << endl; }