結果
問題 |
No.3214 small square
|
ユーザー |
![]() |
提出日時 | 2025-07-26 00:46:11 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 13,361 bytes |
コンパイル時間 | 2,426 ms |
コンパイル使用メモリ | 155,912 KB |
実行使用メモリ | 44,720 KB |
最終ジャッジ日時 | 2025-07-26 00:46:35 |
合計ジャッジ時間 | 20,555 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 WA * 3 |
ソースコード
#include <iostream> #include <iomanip> #include <cassert> #include <vector> #include <algorithm> #include <utility> #include <numeric> #include <tuple> #include <ranges> namespace ranges = std::ranges; namespace views = std::views; // #include "Src/Number/IntegerDivision.hpp" // #include "Src/Utility/BinarySearch.hpp" #include <cstdint> #include <cstddef> 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 <iterator> #include <limits> namespace zawa { template <class T> class CompressedSequence { public: static constexpr u32 NotFound = std::numeric_limits<u32>::max(); CompressedSequence() = default; template <class InputIterator> 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<T>& 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<T> comped() const noexcept { return comped_; } private: std::vector<T> comped_; std::vector<u32> 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 <concepts> namespace zawa { namespace concepts { template <class T> concept Semigroup = requires { typename T::Element; { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>; }; } // namespace concepts } // namespace zawa namespace zawa { namespace concepts { template <class T> concept Identitiable = requires { typename T::Element; { T::identity() } -> std::same_as<typename T::Element>; }; template <class T> concept Monoid = Semigroup<T> and Identitiable<T>; } // namespace } // namespace zawa namespace zawa { namespace concepts { template <class T> concept MonoidWithAction = requires { requires Monoid<typename T::ValueMonoid>; requires Monoid<typename T::OperatorMonoid>; { T::mapping( std::declval<typename T::ValueMonoid::Element>(), std::declval<typename T::OperatorMonoid::Element>() ) } -> std::same_as<typename T::ValueMonoid::Element>; }; } // namespace concepts } // namespace zawa #include <bit> namespace zawa { template <concepts::MonoidWithAction S> 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<V>& 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<usize, usize, usize>; public: template <class F> requires std::predicate<F, V> usize maxRight(usize l, F f) { assert(l <= size()); if (!f(VM::identity())) return l; if (l == size()) return size(); std::vector<NodeInfo> 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 <class F> requires std::predicate<F, V> usize minLeft(usize r, F f) { assert(r <= size()); if (!f(VM::identity())) return r; if (!r) return 0; std::vector<NodeInfo> 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<V> m_dat; std::vector<O> 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<NodeInfo>& 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 <class F> requires std::predicate<F, V> 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 <class F> requires std::predicate<F, V> 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 <optional> struct VM { using Element = long long; static Element identity() { return 0LL; } static Element operation(Element L, Element R) { return max(L, R); } }; 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) { return v + 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; vector<long long> appx, appy; for (int i = 0 ; i < N ; i++) { cin >> X[i] >> Y[i] >> V[i]; X[i] *= 2; Y[i] *= 2; for (int j : {-1, 0, 1}) { appx.push_back(X[i] + j); appy.push_back(Y[i] + j); } } CompressedSequence xs(appx), ys(appy); vector<vector<int>> event(xs.size()); for (int i = 0 ; i < N ; i++) event[xs.at(X[i])].push_back(i); LazySegmentTree<ACT> seg(ys.size()); auto insert = [&](long long y, int v) -> void { seg.operation(ys[y - A], ys.at(y) + 1, v); }; auto erase = [&](long long y, int v) -> void { // cout << "erased " << y << ' ' << v << endl; seg.operation(ys[y - A], ys.at(y) + 1, -v); }; auto eval = [&]() -> long long { return seg.product(0, seg.size()); }; 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]); // cout << "erase " << xs.inverse(j) << ' ' << eval() << endl; ans = max(ans, eval()); j++; } for (int k : event[i]) insert(Y[k], V[k]); ans = max(ans, eval()); // cout << "add " << xs.inverse(j) << ' ' << xs.inverse(i) << ' ' << eval() << endl; // for (int k = 0 ; k < ssize(seg) ; k++) cout << '(' << xs.inverse(k) << ',' << seg[k] << ')'; // cout << endl; } for ( ; j < ssize(event) ; j++) { for (int k : event[j]) erase(Y[k], V[k]); ans = max(ans, eval()); j++; } cout << ans << endl; }