답안 #341786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341786 2020-12-31T03:27:10 Z KoD Bulldozer (JOI17_bulldozer) C++17
75 / 100
859 ms 172984 KB
#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<i32> X(N), Y(N), W(N);
  for (auto i: range(0, N)) {
    std::cin >> X[i] >> Y[i] >> W[i];
  }
  Vec<usize> order(N);
  std::iota(order.begin(), order.end(), (usize) 0);
  std::sort(order.begin(), order.end(), [&](const usize i, const usize j) {
    return X[i] < X[j] || (X[i] == X[j] && Y[i] < Y[j]);
  });
  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)) {
      const auto s = order[i];
      const auto t = order[j];
      if (X[s] != X[t]) {
        vec.emplace_back(Frac(Y[s] - Y[t], X[s] - X[t]), t, s);
      }
    }
  }
  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[order[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[order[i]] = i;
  }
  for (auto &qs: query) {
    for (auto [i, j]: qs) {
      if (inv[i] > inv[j]) {
        std::swap(i, j);
      } 
      S[inv[i] + 1] = S[inv[i]] + W[j];
      S[inv[i] + 2] = S[inv[i] + 1] + W[i];
      seg.assign(inv[i] + 1, type(S[inv[i] + 1]));
      seg.assign(inv[i] + 2, type(S[inv[i] + 2]));
      std::swap(inv[i], inv[j]);
    }
    ans = std::max(ans, seg.fold(0, N + 1).dif);
  }
  std::cout << ans << '\n';
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1024 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 3 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 0 ms 364 KB Output is correct
18 Correct 0 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 0 ms 364 KB Output is correct
21 Correct 2 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 748 KB Output is correct
24 Correct 2 ms 748 KB Output is correct
25 Correct 2 ms 748 KB Output is correct
26 Correct 2 ms 748 KB Output is correct
27 Correct 2 ms 748 KB Output is correct
28 Correct 2 ms 748 KB Output is correct
29 Correct 2 ms 748 KB Output is correct
30 Correct 2 ms 748 KB Output is correct
31 Correct 2 ms 748 KB Output is correct
32 Correct 2 ms 748 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1024 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 3 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 0 ms 364 KB Output is correct
18 Correct 0 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 0 ms 364 KB Output is correct
21 Correct 2 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 748 KB Output is correct
24 Correct 2 ms 748 KB Output is correct
25 Correct 2 ms 748 KB Output is correct
26 Correct 2 ms 748 KB Output is correct
27 Correct 2 ms 748 KB Output is correct
28 Correct 2 ms 748 KB Output is correct
29 Correct 2 ms 748 KB Output is correct
30 Correct 2 ms 748 KB Output is correct
31 Correct 2 ms 748 KB Output is correct
32 Correct 2 ms 748 KB Output is correct
33 Correct 845 ms 172720 KB Output is correct
34 Correct 833 ms 172592 KB Output is correct
35 Correct 839 ms 172796 KB Output is correct
36 Correct 837 ms 172720 KB Output is correct
37 Correct 833 ms 172720 KB Output is correct
38 Correct 826 ms 172848 KB Output is correct
39 Correct 828 ms 172848 KB Output is correct
40 Correct 834 ms 172592 KB Output is correct
41 Correct 837 ms 172848 KB Output is correct
42 Correct 835 ms 172720 KB Output is correct
43 Correct 838 ms 172720 KB Output is correct
44 Correct 825 ms 172848 KB Output is correct
45 Correct 823 ms 172592 KB Output is correct
46 Correct 838 ms 172720 KB Output is correct
47 Correct 825 ms 172720 KB Output is correct
48 Correct 830 ms 172884 KB Output is correct
49 Correct 822 ms 172720 KB Output is correct
50 Correct 827 ms 172764 KB Output is correct
51 Correct 828 ms 172720 KB Output is correct
52 Correct 845 ms 172720 KB Output is correct
53 Correct 824 ms 172720 KB Output is correct
54 Correct 825 ms 172848 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1024 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 2 ms 876 KB Output is correct
7 Correct 3 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 0 ms 364 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 0 ms 364 KB Output is correct
16 Correct 0 ms 364 KB Output is correct
17 Correct 0 ms 364 KB Output is correct
18 Correct 0 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 0 ms 364 KB Output is correct
21 Correct 2 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 748 KB Output is correct
24 Correct 2 ms 748 KB Output is correct
25 Correct 2 ms 748 KB Output is correct
26 Correct 2 ms 748 KB Output is correct
27 Correct 2 ms 748 KB Output is correct
28 Correct 2 ms 748 KB Output is correct
29 Correct 2 ms 748 KB Output is correct
30 Correct 2 ms 748 KB Output is correct
31 Correct 2 ms 748 KB Output is correct
32 Correct 2 ms 748 KB Output is correct
33 Correct 845 ms 172720 KB Output is correct
34 Correct 833 ms 172592 KB Output is correct
35 Correct 839 ms 172796 KB Output is correct
36 Correct 837 ms 172720 KB Output is correct
37 Correct 833 ms 172720 KB Output is correct
38 Correct 826 ms 172848 KB Output is correct
39 Correct 828 ms 172848 KB Output is correct
40 Correct 834 ms 172592 KB Output is correct
41 Correct 837 ms 172848 KB Output is correct
42 Correct 835 ms 172720 KB Output is correct
43 Correct 838 ms 172720 KB Output is correct
44 Correct 825 ms 172848 KB Output is correct
45 Correct 823 ms 172592 KB Output is correct
46 Correct 838 ms 172720 KB Output is correct
47 Correct 825 ms 172720 KB Output is correct
48 Correct 830 ms 172884 KB Output is correct
49 Correct 822 ms 172720 KB Output is correct
50 Correct 827 ms 172764 KB Output is correct
51 Correct 828 ms 172720 KB Output is correct
52 Correct 845 ms 172720 KB Output is correct
53 Correct 824 ms 172720 KB Output is correct
54 Correct 825 ms 172848 KB Output is correct
55 Correct 840 ms 172592 KB Output is correct
56 Correct 828 ms 172592 KB Output is correct
57 Correct 834 ms 172848 KB Output is correct
58 Correct 848 ms 172856 KB Output is correct
59 Correct 826 ms 172728 KB Output is correct
60 Correct 842 ms 172848 KB Output is correct
61 Correct 837 ms 172720 KB Output is correct
62 Correct 837 ms 172984 KB Output is correct
63 Correct 835 ms 172592 KB Output is correct
64 Correct 830 ms 172720 KB Output is correct
65 Correct 841 ms 172720 KB Output is correct
66 Correct 834 ms 172592 KB Output is correct
67 Correct 836 ms 172592 KB Output is correct
68 Correct 829 ms 172720 KB Output is correct
69 Correct 859 ms 172592 KB Output is correct
70 Correct 836 ms 172664 KB Output is correct
71 Correct 845 ms 172592 KB Output is correct
72 Correct 824 ms 172888 KB Output is correct
73 Correct 843 ms 172748 KB Output is correct
74 Correct 827 ms 172592 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -