結果
問題 |
No.3214 small square
|
ユーザー |
![]() |
提出日時 | 2025-07-26 01:44:02 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 15,250 bytes |
コンパイル時間 | 2,978 ms |
コンパイル使用メモリ | 172,688 KB |
実行使用メモリ | 47,352 KB |
最終ジャッジ日時 | 2025-07-26 01:44:36 |
合計ジャッジ時間 | 26,923 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
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; long long A, X[200020], Y[200020], V[200020]; long long solve() { vector<long long> appx, appy; for (int i = 0 ; i < N ; i++) { for (long long j : {-A, 0LL, 1LL}) { appx.push_back(2LL * (j + X[i])); appy.push_back(2LL * (j + Y[i])); } } CompressedSequence xs(appx), ys(appy); vector<vector<int>> event(xs.size()); for (int i = 0 ; i < N ; i++) event[xs.at(2 * X[i])].push_back(i); LazySegmentTree<ACT> seg(ys.size()); auto insert = [&](long long y, int v) -> void { // cout << "inserted " << y << ' ' << v << endl; seg.operation(ys[2 * (y - A)], ys.at(2 * y) + 1, v); }; auto erase = [&](long long y, int v) -> void { // cout << "erased " << y << ' ' << v << endl; seg.operation(ys[2 * (y - A)], ys.at(2 * 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) ; ) { while (xs.inverse(j) + 2 * A < xs.inverse(i)) { for (int k : event[j]) erase(Y[k], V[k]); // if (event[j].size()) cout << "erased " << xs.inverse(j) << endl; // for (int k = 0 ; k < ssize(ys) ; k++) cout << seg[k] << ' '; // cout << endl; // ans = max(ans, eval()); j++; } while (i < ssize(xs) and xs.inverse(j) + 2 * A >= xs.inverse(i)) { for (int k : event[i]) insert(Y[k], V[k]); // if (event[i].size()) cout << "inserted " << xs.inverse(i) << endl; i++; } // for (int k = 0 ; k < ssize(ys) ; k++) cout << seg[k] << ' '; // cout << endl; assert(i == ssize(xs) or xs.inverse(j) + 2 * A < xs.inverse(i)); ans = max(ans, eval()); } for ( ; j < ssize(event) ; j++) { for (int k : event[j]) erase(Y[k], V[k]); ans = max(ans, eval()); } // for (int i = 0 ; i < ssize(ys) ; i++) cout << ys.inverse(i) << ' '; // cout << endl; return ans; } long long naive() { long long L = (int)1e9, R = -L, D = (int)1e9, U = -D; for (int i = 0 ; i < N ; i++) { L = min(L, X[i]); R = max(R, X[i]); D = min(D, Y[i]); U = max(U, Y[i]); } long long ans = 0; int p = (int)1e9, q = (int)1e9; for (int x = L - A - 100 ; x <= R + A + 100 ; x++) { for (int y = D - A - 100 ; y <= R + A + 100 ; y++) { long long cur = 0; for (int i = 0 ; i < N ; i++) { if (x <= X[i] and X[i] <= x + A and y <= Y[i] and Y[i] <= y + A) { cur += V[i]; } } if (ans < cur) { ans = cur; p = x; q = y; } ans = max<long long>(ans, cur); } } return ans; } #include <random> std::mt19937 mt{std::random_device{}()}; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); #ifdef DEBUG while (true) { N = mt() % 5 + 1; A = mt() % 10 + 1; cout << "---------------------" << endl; cout << N << ' ' << A << endl; for (int i = 0 ; i < N ; i++) { X[i] = mt() % 10 + 1; Y[i] = mt() % 10 + 1; V[i] = mt() % 21 - 10; cout << X[i] << ' ' << Y[i] << ' ' << V[i] << endl; } long long my = solve(), ans = naive(); if (my != ans) { cerr << ans << " but output " << my << endl; exit(0); } } #else cin >> N >> A; for (int i = 0 ; i < N ; i++) cin >> X[i] >> Y[i] >> V[i]; cout << solve() << endl; #endif }