comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: test/atcoder/abc298_f.test.cpp

Depends on

Code

// 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_();
}
Back to top page