제출 #341790

#제출 시각아이디문제언어결과실행 시간메모리
341790KoDBulldozer (JOI17_bulldozer)C++17
100 / 100
720 ms172992 KiB
#line 1 "main.cpp" /** * @title Template */ #include <iostream> #include <algorithm> #include <utility> #include <numeric> #include <vector> #include <array> #include <cassert> #include <map> #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp" #line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp" class range { struct iter { std::size_t itr; constexpr iter(std::size_t pos) noexcept: itr(pos) { } constexpr void operator ++ () noexcept { ++itr; } constexpr bool operator != (iter other) const noexcept { return itr != other.itr; } constexpr std::size_t operator * () const noexcept { return itr; } }; struct reviter { std::size_t itr; constexpr reviter(std::size_t pos) noexcept: itr(pos) { } constexpr void operator ++ () noexcept { --itr; } constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; } constexpr std::size_t operator * () const noexcept { return itr; } }; const iter first, last; public: constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { } constexpr iter begin() const noexcept { return first; } constexpr iter end() const noexcept { return last; } constexpr reviter rbegin() const noexcept { return reviter(*last - 1); } constexpr reviter rend() const noexcept { return reviter(*first - 1); } }; /** * @title Range */ #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/container/segment_tree.cpp" #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/monoid.cpp" #include <type_traits> #line 5 "/Users/kodamankod/Desktop/cpp_programming/Library/other/monoid.cpp" #include <stdexcept> template <class T, class = void> class has_identity: public std::false_type { }; template <class T> class has_identity<T, typename std::conditional<false, decltype(T::identity()), void>::type>: public std::true_type { }; template <class T> constexpr typename std::enable_if<has_identity<T>::value, typename T::type>::type empty_exception() { return T::identity(); } template <class T> [[noreturn]] typename std::enable_if<!has_identity<T>::value, typename T::type>::type empty_exception() { throw std::runtime_error("type T has no identity"); } template <class T, bool HasIdentity> class fixed_monoid_impl: public T { public: using type = typename T::type; static constexpr type convert(const type &value) { return value; } static constexpr type revert(const type &value) { return value; } template <class Mapping, class Value, class... Args> static constexpr void operate(Mapping &&func, Value &value, const type &op, Args&&... args) { value = func(value, op, std::forward<Args>(args)...); } template <class Constraint> static constexpr bool satisfies(Constraint &&func, const type &value) { return func(value); } }; template <class T> class fixed_monoid_impl<T, false> { public: class type { public: typename T::type value; bool state; explicit constexpr type(): value(typename T::type { }), state(false) { } explicit constexpr type(const typename T::type &value): value(value), state(true) { } }; static constexpr type convert(const typename T::type &value) { return type(value); } static constexpr typename T::type revert(const type &value) { if (!value.state) throw std::runtime_error("attempted to revert identity to non-monoid"); return value.value; } static constexpr type identity() { return type(); } static constexpr type operation(const type &v1, const type &v2) { if (!v1.state) return v2; if (!v2.state) return v1; return type(T::operation(v1.value, v2.value)); } template <class Mapping, class Value, class... Args> static constexpr void operate(Mapping &&func, Value &value, const type &op, Args&&... args) { if (!op.state) return; value = func(value, op.value, std::forward<Args>(args)...); } template <class Constraint> static constexpr bool satisfies(Constraint &&func, const type &value) { if (!value.state) return false; return func(value.value); } }; template <class T> using fixed_monoid = fixed_monoid_impl<T, has_identity<T>::value>; /** * @title Monoid Utility */ #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/bit_operation.cpp" #include <cstddef> #include <cstdint> constexpr size_t bit_ppc(const uint64_t x) { return __builtin_popcountll(x); } constexpr size_t bit_ctzr(const uint64_t x) { return x == 0 ? 64 : __builtin_ctzll(x); } constexpr size_t bit_ctzl(const uint64_t x) { return x == 0 ? 64 : __builtin_clzll(x); } constexpr size_t bit_width(const uint64_t x) { return 64 - bit_ctzl(x); } constexpr uint64_t bit_msb(const uint64_t x) { return x == 0 ? 0 : uint64_t(1) << (bit_width(x) - 1); } constexpr uint64_t bit_lsb(const uint64_t x) { return x & (-x); } constexpr uint64_t bit_cover(const uint64_t x) { return x == 0 ? 0 : bit_msb(2 * x - 1); } constexpr uint64_t bit_rev(uint64_t x) { x = ((x >> 1) & 0x5555555555555555) | ((x & 0x5555555555555555) << 1); x = ((x >> 2) & 0x3333333333333333) | ((x & 0x3333333333333333) << 2); x = ((x >> 4) & 0x0F0F0F0F0F0F0F0F) | ((x & 0x0F0F0F0F0F0F0F0F) << 4); x = ((x >> 8) & 0x00FF00FF00FF00FF) | ((x & 0x00FF00FF00FF00FF) << 8); x = ((x >> 16) & 0x0000FFFF0000FFFF) | ((x & 0x0000FFFF0000FFFF) << 16); x = (x >> 32) | (x << 32); return x; } /** * @title Bit Operations */ #line 5 "/Users/kodamankod/Desktop/cpp_programming/Library/container/segment_tree.cpp" #line 8 "/Users/kodamankod/Desktop/cpp_programming/Library/container/segment_tree.cpp" #include <iterator> #line 11 "/Users/kodamankod/Desktop/cpp_programming/Library/container/segment_tree.cpp" #include <type_traits> #line 13 "/Users/kodamankod/Desktop/cpp_programming/Library/container/segment_tree.cpp" template <class Monoid> class segment_tree { public: using structure = Monoid; using value_monoid = typename Monoid::value_structure; using value_type = typename Monoid::value_structure::type; using size_type = size_t; private: using fixed_value_monoid = fixed_monoid<value_monoid>; using fixed_value_type = typename fixed_value_monoid::type; std::vector<fixed_value_type> M_tree; void M_fix_change(const size_type index) { M_tree[index] = fixed_value_monoid::operation(M_tree[index << 1 | 0], M_tree[index << 1 | 1]); } public: segment_tree() = default; explicit segment_tree(const size_type size) { initialize(size); } template <class InputIterator> explicit segment_tree(InputIterator first, InputIterator last) { construct(first, last); } void initialize(const size_type size) { clear(); M_tree.assign(size << 1, fixed_value_monoid::identity()); } template <class InputIterator> void construct(InputIterator first, InputIterator last) { clear(); const size_type size = std::distance(first, last); M_tree.reserve(size << 1); M_tree.assign(size, fixed_value_monoid::identity()); std::transform(first, last, std::back_inserter(M_tree), [&](const value_type &value) { return fixed_value_monoid::convert(value); }); for (size_type index = size - 1; index != 0; --index) { M_fix_change(index); } } void assign(size_type index, const value_type &value) { assert(index < size()); index += size(); M_tree[index] = fixed_value_monoid::convert(value); while (index != 1) { index >>= 1; M_fix_change(index); } } value_type at(const size_type index) const { assert(index < size()); return fixed_value_monoid::revert(M_tree[index + size()]); } value_type fold(size_type first, size_type last) const { assert(first <= last); assert(last <= size()); first += size(); last += size(); fixed_value_type fold_l = fixed_value_monoid::identity(); fixed_value_type fold_r = fixed_value_monoid::identity(); while (first != last) { if (first & 1) { fold_l = fixed_value_monoid::operation(fold_l, M_tree[first]); ++first; } if (last & 1) { --last; fold_r = fixed_value_monoid::operation(M_tree[last], fold_r); } first >>= 1; last >>= 1; } return fixed_value_monoid::revert(fixed_value_monoid::operation(fold_l, fold_r)); } template <bool ToRight = true, class Constraint, std::enable_if_t<ToRight>* = nullptr> size_type satisfies(const size_type left, Constraint &&func) const { assert(left <= size()); if (fixed_value_monoid::satisfies(std::forward<Constraint>(func), fixed_value_monoid::identity())) return left; size_type first = left + size(); size_type last = 2 * size(); const size_type last_c = last; fixed_value_type fold = fixed_value_monoid::identity(); const auto try_merge = [&](const size_type index) { fixed_value_type tmp = fixed_value_monoid::operation(fold, M_tree[index]); if (fixed_value_monoid::satisfies(std::forward<Constraint>(func), tmp)) return true; fold = std::move(tmp); return false; }; const auto subtree = [&](size_type index) { while (index < size()) { index <<= 1; if (!try_merge(index)) ++index; } return index - size() + 1; }; size_type story = 0; while (first < last) { if (first & 1) { if (try_merge(first)) return subtree(first); ++first; } first >>= 1; last >>= 1; ++story; } while (story--) { last = last_c >> story; if (last & 1) { --last; if (try_merge(last)) return subtree(last); } } return size() + 1; } template <bool ToRight = true, class Constraint, std::enable_if_t<!ToRight>* = nullptr> size_type satisfies(const size_type right, Constraint &&func) const { assert(right <= size()); if (fixed_value_monoid::satisfies(std::forward<Constraint>(func), fixed_value_monoid::identity())) return right; size_type first = size(); size_type last = right + size(); const size_type first_c = first; fixed_value_type fold = fixed_value_monoid::identity(); const auto try_merge = [&](const size_type index) { fixed_value_type tmp = fixed_value_monoid::operation(M_tree[index], fold); if (fixed_value_monoid::satisfies(std::forward<Constraint>(func), tmp)) return true; fold = std::move(tmp); return false; }; const auto subtree = [&](size_type index) { while (index < size()) { index <<= 1; if (try_merge(index + 1)) ++index; } return index - size(); }; size_type story = 0; while (first < last) { if (first & 1) ++first; if (last & 1) { --last; if (try_merge(last)) return subtree(last); } first >>= 1; last >>= 1; ++story; } const size_type cover = bit_cover(first_c); while (story--) { first = (cover >> story) - ((cover - first_c) >> story); if (first & 1) { if (try_merge(first)) return subtree(first); } } return size_type(-1); } void clear() { M_tree.clear(); M_tree.shrink_to_fit(); } size_type size() const { return M_tree.size() >> 1; } }; /** * @title Segment Tree */ #line 17 "main.cpp" using i32 = std::int32_t; using i64 = std::int64_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using isize = std::ptrdiff_t; using usize = std::size_t; constexpr i32 inf32 = (u32) ~0 >> 2; constexpr i64 inf64 = (u64) ~0 >> 2; struct st_monoid { struct value_structure { struct type { i64 max, min, dif; explicit type(const i64 value): max(value), min(value), dif(0) { } explicit type(const i64 max, const i64 min, const i64 dif): max(max), min(min), dif(dif) { } }; static type identity() { return type(-inf64, inf64, -inf64); } static type operation(const type& v1, const type& v2) { return type(std::max(v1.max, v2.max), std::min(v1.min, v2.min), std::max({ v2.max - v1.min, v1.dif, v2.dif})); } }; }; template <class T> using Vec = std::vector<T>; struct Frac { i64 a, b; Frac(const i64 x, const i64 y): a(x), b(y) { if (b < 0) { a = -a; b = -b; } } bool operator < (const Frac &other) const { return a * other.b < other.a * b; } bool operator > (const Frac &other) const { return a * other.b > other.a * b; } bool operator == (const Frac &other) const { return a * other.b == other.a * b; } }; constexpr i64 INF = 2000000005; int main() { usize N; std::cin >> N; Vec<std::tuple<i32, i32, i32>> points(N); for (auto &[a, b, c]: points) { std::cin >> a >> b >> c; } std::sort(points.begin(), points.end()); Vec<i32> X(N), Y(N), W(N); for (auto i: range(0, N)) { const auto [a, b, c] = points[i]; X[i] = a; Y[i] = b; W[i] = c; } Vec<std::tuple<Frac, usize, usize>> vec; vec.reserve(N * (N - 1) / 2); for (auto i: range(0, N)) { for (auto j: range(0, i)) { if (X[i] != X[j]) { vec.emplace_back(Frac(Y[i] - Y[j], X[i] - X[j]), j, i); } } } std::sort(vec.begin(), vec.end()); Vec<Vec<std::pair<usize, usize>>> query; { Frac last(-1, INF); for (const auto [f, i, j]: vec) { if (!(f == last)) { last = f; query.push_back({ }); } query.back().emplace_back(i, j); } } Vec<i64> S(N + 1); for (auto i: range(0, N)) { S[i + 1] = S[i] + W[i]; } using type = typename st_monoid::value_structure::type; segment_tree<st_monoid> seg(N + 1); for (auto i: range(0, N + 1)) { seg.assign(i, type(S[i])); } i64 ans = seg.fold(0, N + 1).dif; Vec<usize> inv(N); for (auto i: range(0, N)) { inv[i] = i; } for (auto &qs: query) { for (auto [i, j]: qs) { S[inv[i] + 1] = S[inv[i]] + W[j]; seg.assign(inv[i] + 1, type(S[inv[i] + 1])); std::swap(inv[i], inv[j]); } ans = std::max(ans, seg.fold(0, N + 1).dif); } std::cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...