This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://atcoder.jp/contests/abc266/tasks/abc266_Ex" #include "library/datastructure/segment_tree/compressed_segment_tree.hpp" #include <iostream> #include <limits> long long op(long long x, long long y) { return std::max(x, y); } long long e() { return std::numeric_limits<long long>::min() / 2; } using CubeMaxQuery = suisen::CompressedSegmentTree<long long, op, e, 3>; constexpr int inf = std::numeric_limits<int>::max() / 2; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<std::tuple<int, int, int, int>> ps(n); for (int i = 0; i < n; ++i) { int t, x, y, a; std::cin >> t >> x >> y >> a; ps[i] = { y, t - y + x, t - y - x, a }; } std::sort(ps.begin(), ps.end()); CubeMaxQuery seg; seg.add_point({ 0, 0, 0 }); for (auto [x, y, z, val] : ps) { seg.add_point({ x, y, z }); } seg.build(); seg.set({ 0, 0, 0 }, op(seg.get({ 0, 0, 0 }), 0)); long long ans = 0; for (auto [x, y, z, val] : ps) { long long p = seg.query({ std::pair{ -inf, x + 1 }, std::pair{ -inf, y + 1 }, std::pair{ -inf, z + 1 } }); ans = std::max(ans, p + val); seg.set({ x, y, z }, op(seg.get({ x, y, z }), p + val)); } std::cout << ans << std::endl; return 0; }
#line 1 "test/src/datastructure/segment_tree/compressed_segment_tree/abc266_h.test.cpp" #define PROBLEM "https://atcoder.jp/contests/abc266/tasks/abc266_Ex" #line 1 "library/datastructure/segment_tree/compressed_segment_tree.hpp" #include <algorithm> #include <array> #include <vector> namespace suisen { namespace internal::compressed_segment_tree { template <typename T> struct Compressor { using value_type = T; Compressor() = default; void add(const value_type& x) { xs.push_back(x); } int build() { std::sort(xs.begin(), xs.end()); xs.erase(std::unique(xs.begin(), xs.end()), xs.end()); return xs.size(); } int operator()(const value_type& x) const { return std::lower_bound(xs.begin(), xs.end(), x) - xs.begin(); } private: std::vector<value_type> xs; }; } template <typename T, T(*op)(T, T), T(*e)(), std::size_t K = 1, typename Index = int> struct CompressedSegmentTree { using value_type = T; using index_type = Index; using point_type = std::array<index_type, K>; using cube_type = std::array<std::pair<index_type, index_type>, K>; using data_type = CompressedSegmentTree<value_type, op, e, K - 1, index_type>; CompressedSegmentTree() = default; void add_point(const point_type& p) { comp.add(p[0]); points.push_back(p); } void build() { n = comp.build(); data.assign(2 * n, data_type{}); for (const auto& p : points) for (int k = n + comp(p[0]); k; k >>= 1) { data[k].add_point(tail(p)); } points.clear(); points.shrink_to_fit(); for (auto& t : data) t.build(); } value_type query(const cube_type& p) const { value_type sml = e(), smr = e(); int l = comp(p[0].first) + n, r = comp(p[0].second) + n; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) sml = op(sml, data[l++].query(tail(p))); if (r & 1) smr = op(data[--r].query(tail(p)), smr); } return op(sml, smr); } value_type get(const point_type& p) const { return data[comp(p[0]) + n].get(tail(p)); } void set(const point_type& p, const value_type& val) { for (int i = comp(p[0]) + n; i; i >>= 1) data[i].set(tail(p), val); } void apply(const point_type& p, const value_type& val) { for (int i = comp(p[0]) + n; i; i >>= 1) data[i].apply(tail(p), val); } private: int n; internal::compressed_segment_tree::Compressor<index_type> comp; std::vector<point_type> points; std::vector<data_type> data; template <typename X> static constexpr auto tail(const X& p) { return tail_impl(p, std::make_index_sequence<K - 1>{}); } template <typename X, std::size_t... Seq> static constexpr auto tail_impl(const X& p, std::index_sequence<Seq...>) { return std::conditional_t<std::is_same_v<X, point_type>, typename data_type::point_type, typename data_type::cube_type>{ p[1 + Seq]... }; } }; template <typename T, T(*op)(T, T), T(*e)(), typename Index> struct CompressedSegmentTree<T, op, e, std::size_t(1), Index> { using value_type = T; using index_type = Index; using point_type = index_type; using cube_type = std::pair<index_type, index_type>; using data_type = value_type; CompressedSegmentTree() = default; void add_point(const point_type& p) { comp.add(p); } void build() { n = comp.build(); data.assign(2 * n, e()); } value_type query(const index_type& l, const index_type& r) const { return query({ l, r }); } value_type query(const cube_type& p) const { value_type sml = e(), smr = e(); int l = comp(p.first) + n, r = comp(p.second) + n; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) sml = op(sml, data[l++]); if (r & 1) smr = op(data[--r], smr); } return op(sml, smr); } value_type get(const point_type &i) const { return data[comp(i) + n]; } void set(const point_type& p, const value_type& val) { int i = comp(p) + n; data[i] = val; while (i >>= 1) data[i] = op(data[2 * i + 0], data[2 * i + 1]); } void apply(const point_type& p, const value_type& val) { for (int i = comp(p) + n; i; i >>= 1) data[i] = op(data[i], val); } private: int n; internal::compressed_segment_tree::Compressor<index_type> comp; std::vector<data_type> data; }; } // namespace suisen #line 4 "test/src/datastructure/segment_tree/compressed_segment_tree/abc266_h.test.cpp" #include <iostream> #include <limits> long long op(long long x, long long y) { return std::max(x, y); } long long e() { return std::numeric_limits<long long>::min() / 2; } using CubeMaxQuery = suisen::CompressedSegmentTree<long long, op, e, 3>; constexpr int inf = std::numeric_limits<int>::max() / 2; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; std::vector<std::tuple<int, int, int, int>> ps(n); for (int i = 0; i < n; ++i) { int t, x, y, a; std::cin >> t >> x >> y >> a; ps[i] = { y, t - y + x, t - y - x, a }; } std::sort(ps.begin(), ps.end()); CubeMaxQuery seg; seg.add_point({ 0, 0, 0 }); for (auto [x, y, z, val] : ps) { seg.add_point({ x, y, z }); } seg.build(); seg.set({ 0, 0, 0 }, op(seg.get({ 0, 0, 0 }), 0)); long long ans = 0; for (auto [x, y, z, val] : ps) { long long p = seg.query({ std::pair{ -inf, x + 1 }, std::pair{ -inf, y + 1 }, std::pair{ -inf, z + 1 } }); ans = std::max(ans, p + val); seg.set({ x, y, z }, op(seg.get({ x, y, z }), p + val)); } std::cout << ans << std::endl; return 0; }