This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub luzhiled1333/comp-library
// verification-helper: PROBLEM https://atcoder.jp/contests/abc298/tasks/abc298_f #include "src/cpp-template/header/change-max.hpp" #include "src/cpp-template/header/int-alias.hpp" #include "src/cpp-template/header/rep.hpp" #include "src/cpp-template/header/size-alias.hpp" #include "src/data-structure/segment-tree/presets/range-maximum-query-solver.hpp" #include "src/sequence/compression.hpp" #include <algorithm> #include <iostream> #include <vector> namespace luz { void main_() { usize n; std::cin >> n; std::vector< usize > rs, cs; std::vector< i32 > xs(n); { // input and compression std::vector< u32 > as(n), bs(n); for (usize i: rep(0, n)) { std::cin >> as[i] >> bs[i] >> xs[i]; } Compressor< u32 > r_cp(as), c_cp(bs); rs = r_cp.compressed_vector(); cs = c_cp.compressed_vector(); } std::vector< std::tuple< usize, usize, i32 > > qs(n); for (usize i: rep(0, n)) { qs[i] = {rs[i], cs[i], xs[i]}; } std::sort(qs.begin(), qs.end()); RangeMaximumQuerySolver< i64 > seg(n, 0); auto seg_add = [&](usize idx, i64 x) { seg.set(idx, seg.fold(idx) + x); }; for (usize i: rep(0, n)) { seg_add(cs[i], xs[i]); } usize m = *max_element(rs.begin(), rs.end()) + 1; i64 ans = 0; usize idx = 0; for (usize r: rep(0, m)) { usize prev_idx = idx; i64 max = 0; while (idx < qs.size() and std::get< 0 >(qs[idx]) == r) { i32 x = std::get< 2 >(qs[idx]); max += x; i32 c = std::get< 1 >(qs[idx]); seg_add(c, -x); idx++; } max += seg.fold_all(); chmax(ans, max); for (usize i: rep(prev_idx, idx)) { auto [_, c, x] = qs[i]; seg_add(c, x); } } std::cout << ans << std::endl; } } // namespace luz int main() { luz::main_(); }
#line 1 "test/atcoder/abc298_f.test.cpp" // verification-helper: PROBLEM https://atcoder.jp/contests/abc298/tasks/abc298_f #line 2 "src/cpp-template/header/change-max.hpp" namespace luz { template < typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b and (a = b, true); } } // namespace luz #line 2 "src/cpp-template/header/int-alias.hpp" #include <cstdint> namespace luz { using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using u128 = __uint128_t; } // namespace luz #line 2 "src/cpp-template/header/rep.hpp" #line 2 "src/cpp-template/header/size-alias.hpp" #include <cstddef> namespace luz { using isize = std::ptrdiff_t; using usize = std::size_t; } // namespace luz #line 4 "src/cpp-template/header/rep.hpp" #include <algorithm> namespace luz { struct rep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { ++i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rep(const usize f, const usize l) noexcept : f(std::min(f, l)), l(l) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; struct rrep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { --i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rrep(const usize f, const usize l) noexcept : f(l - 1), l(std::min(f, l) - 1) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; } // namespace luz #line 2 "src/data-structure/segment-tree/presets/range-maximum-query-solver.hpp" #line 2 "src/data-structure/segment-tree/point-mapping-range-fold-segment-tree.hpp" #line 5 "src/data-structure/segment-tree/point-mapping-range-fold-segment-tree.hpp" #include <cassert> #include <vector> namespace luz { template < class value_structure > class PointMappingRangeFoldSegmentTree { using V = value_structure; using VT = typename V::value_type; std::vector< VT > tree; void evaluate(usize index) { tree[index] = V::operation(tree[index << 1 | 0], tree[index << 1 | 1]); } public: using value_type = VT; PointMappingRangeFoldSegmentTree() = default; explicit PointMappingRangeFoldSegmentTree(const usize n) : tree(n * 2, V::identity()) {} explicit PointMappingRangeFoldSegmentTree(const usize n, VT v) : PointMappingRangeFoldSegmentTree(n) { build(std::vector< VT >(n, v)); } explicit PointMappingRangeFoldSegmentTree( const std::vector< VT > &vs) : PointMappingRangeFoldSegmentTree(vs.size()) { build(vs); } void build(const std::vector< VT > &vs) { usize n = vs.size(); assert(2 * n == tree.size()); std::copy(vs.begin(), vs.end(), tree.begin() + n); for (usize index: rrep(1, n)) { evaluate(index); } } usize size() const { return tree.size() / 2; } void set(usize index, const VT x) { assert(index < size()); index += size(); tree[index] = x; while (index != 1) { index >>= 1; evaluate(index); } } VT fold(usize index) const { assert(index < size()); return tree[index + size()]; } VT fold(usize first, usize last) const { assert(first <= last); assert(last <= size()); first += size(); last += size(); VT fold_l = V::identity(); VT fold_r = V::identity(); while (first != last) { if (first & 1) { fold_l = V::operation(fold_l, tree[first]); first += 1; } first >>= 1; if (last & 1) { last -= 1; fold_r = V::operation(tree[last], fold_r); } last >>= 1; } return V::operation(fold_l, fold_r); } VT fold_all() const { return (size() ? tree[1] : V::identity()); } }; template < class value_structure > using SegmentTree = PointMappingRangeFoldSegmentTree< value_structure >; } // namespace luz #line 2 "src/data-structure/segment-tree/presets/monoid/value-structure-maximum.hpp" #line 4 "src/data-structure/segment-tree/presets/monoid/value-structure-maximum.hpp" #include <limits> namespace luz::monoid { template < typename T > class RangeMaximumQueryMonoid { static constexpr T identity_{std::numeric_limits< T >::min()}; public: using value_type = T; static constexpr T operation(T a, T b) { return std::max(a, b); } static constexpr T identity() { return identity_; } }; } // namespace luz::monoid #line 5 "src/data-structure/segment-tree/presets/range-maximum-query-solver.hpp" namespace luz { template < typename T > using RangeMaximumQuerySolver = SegmentTree< monoid::RangeMaximumQueryMonoid< T > >; } // namespace luz #line 2 "src/sequence/compression.hpp" #line 5 "src/sequence/compression.hpp" #line 8 "src/sequence/compression.hpp" #include <functional> #line 10 "src/sequence/compression.hpp" namespace luz { template < class T, class Compare = std::less< T > > class Compressor { std::vector< T > vs; std::vector< T > zip; std::vector< usize > ziped_vs; public: explicit Compressor(std::vector< T > vs) : vs(vs), zip(vs), ziped_vs(vs.size()) { std::sort(zip.begin(), zip.end(), Compare()); zip.erase(std::unique(zip.begin(), zip.end()), zip.end()); for (usize i: rep(0, vs.size())) { ziped_vs[i] = compress(vs[i]); } } std::vector< usize > compressed_vector() const { return ziped_vs; } usize compress(T v) const { auto iter = std::lower_bound(zip.begin(), zip.end(), v); assert(*iter == v); return iter - zip.begin(); } T expand(usize i) const { assert(i < zip.size()); return zip[i]; } }; } // namespace luz #line 9 "test/atcoder/abc298_f.test.cpp" #line 11 "test/atcoder/abc298_f.test.cpp" #include <iostream> #line 13 "test/atcoder/abc298_f.test.cpp" namespace luz { void main_() { usize n; std::cin >> n; std::vector< usize > rs, cs; std::vector< i32 > xs(n); { // input and compression std::vector< u32 > as(n), bs(n); for (usize i: rep(0, n)) { std::cin >> as[i] >> bs[i] >> xs[i]; } Compressor< u32 > r_cp(as), c_cp(bs); rs = r_cp.compressed_vector(); cs = c_cp.compressed_vector(); } std::vector< std::tuple< usize, usize, i32 > > qs(n); for (usize i: rep(0, n)) { qs[i] = {rs[i], cs[i], xs[i]}; } std::sort(qs.begin(), qs.end()); RangeMaximumQuerySolver< i64 > seg(n, 0); auto seg_add = [&](usize idx, i64 x) { seg.set(idx, seg.fold(idx) + x); }; for (usize i: rep(0, n)) { seg_add(cs[i], xs[i]); } usize m = *max_element(rs.begin(), rs.end()) + 1; i64 ans = 0; usize idx = 0; for (usize r: rep(0, m)) { usize prev_idx = idx; i64 max = 0; while (idx < qs.size() and std::get< 0 >(qs[idx]) == r) { i32 x = std::get< 2 >(qs[idx]); max += x; i32 c = std::get< 1 >(qs[idx]); seg_add(c, -x); idx++; } max += seg.fold_all(); chmax(ans, max); for (usize i: rep(prev_idx, idx)) { auto [_, c, x] = qs[i]; seg_add(c, x); } } std::cout << ans << std::endl; } } // namespace luz int main() { luz::main_(); }