test/yosupo-judge/segment_add_get_min/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://judge.yosupo.jp/problem/segment_add_get_min
• Link: View error logs on GitHub Actions

Depends on

• LiChao segment tree (Mylib/DataStructure/ConvexHullTrick/lichao_segment_tree.cpp)
• Input tuple (Mylib/IO/input_tuple.cpp)
• Input tuples (Mylib/IO/input_tuples.cpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min"

#include <iostream>
#include <tuple>
#include <utility>
#include <variant>
#include <vector>
#include "Mylib/DataStructure/ConvexHullTrick/lichao_segment_tree.cpp"
#include "Mylib/IO/input_tuples.cpp"

namespace hl = haar_lib;

using Segment = std::tuple<int64_t, int64_t, int64_t, int64_t>;
using Query   = std::variant<Segment, int64_t>;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;

  std::vector<int64_t> xs;

  std::vector<Segment> lines;

  for (auto [l, r, a, b] : hl::input_tuples<int64_t, int64_t, int64_t, int64_t>(N)) {
    lines.emplace_back(l, r, a, b);
  }

  std::vector<Query> query;

  for (auto [type] : hl::input_tuples<int>(Q)) {
    switch (type) {
      case 0: {
        int64_t l, r, a, b;
        std::cin >> l >> r >> a >> b;
        query.push_back(Segment({l, r, a, b}));
        break;
      }
      case 1: {
        int64_t p;
        std::cin >> p;
        query.push_back(p);
        xs.push_back(p);
        break;
      }
    }
  }

  if (not xs.empty()) {
    auto lc = hl::make_lichao_min(xs);

    for (auto [l, r, a, b] : lines) {
      lc.add_segment(l, r, a, b);
    }

    for (auto &q : query) {
      if (q.index() == 0) {
        auto [l, r, a, b] = std::get<0>(q);
        lc.add_segment(l, r, a, b);
      } else {
        auto p   = std::get<1>(q);
        auto res = lc(p);

        if (res) {
          std::cout << *res << "\n";
        } else {
          std::cout << "INFINITY"
                    << "\n";
        }
      }
    }
  }

  return 0;
}

#line 1 "test/yosupo-judge/segment_add_get_min/main.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/segment_add_get_min"

#include <iostream>
#include <tuple>
#include <utility>
#include <variant>
#include <vector>
#line 2 "Mylib/DataStructure/ConvexHullTrick/lichao_segment_tree.cpp"
#include <algorithm>
#include <optional>
#line 6 "Mylib/DataStructure/ConvexHullTrick/lichao_segment_tree.cpp"

namespace haar_lib {
  template <typename T, typename Comparator>
  class lichao_segment_tree {
  public:
    using value_type = T;

  private:
    using line = std::pair<T, T>;

    Comparator cmp_ = Comparator();
    std::vector<T> xs_;
    int n_;
    std::vector<std::optional<line>> data_;
    std::vector<std::pair<int, int>> range_;

    T chm(const T &a, const T &b) const {
      return cmp_(a, b) ? a : b;
    }

    void init_range_(int i, int left, int right) {
      if (i >= 2 * n_) return;

      range_[i]     = std::make_pair(left, right);
      const int mid = (left + right) / 2;
      init_range_(i << 1 | 0, left, mid);
      init_range_(i << 1 | 1, mid, right);
    }

  public:
    lichao_segment_tree() {}
    lichao_segment_tree(std::vector<T> xs) : xs_(xs) {
      std::sort(xs_.begin(), xs_.end());
      xs_.erase(std::unique(xs_.begin(), xs_.end()), xs_.end());

      n_ = 1;
      while (n_ < (int) xs_.size()) n_ *= 2;

      const auto m = xs_.back();
      xs_.resize(n_, m);

      data_.assign(2 * n_, std::nullopt);

      range_.resize(2 * n_);
      init_range_(1, 0, n_);
    }

    T apply(const line &l, const T &x) const {
      return l.first * x + l.second;
    }

  private:
    void update(int i, line new_line, int l, int r) {
      if (not data_[i]) {
        data_[i] = new_line;
        return;
      }

      const int m = (l + r) / 2;

      auto lx = xs_[l], mx = xs_[m], rx = xs_[r - 1];

      bool left  = cmp_(apply(new_line, lx), apply(*data_[i], lx));
      bool mid   = cmp_(apply(new_line, mx), apply(*data_[i], mx));
      bool right = cmp_(apply(new_line, rx), apply(*data_[i], rx));

      if (left and right) {
        data_[i] = new_line;
        return;
      }

      if (not left and not right) {
        return;
      }

      if (mid) {
        std::swap(*data_[i], new_line);
      }

      if (left != mid) {
        update(i << 1 | 0, new_line, l, m);
      } else {
        update(i << 1 | 1, new_line, m, r);
      }
    }

  public:
    void add_line(T a, T b) {
      update(1, std::make_pair(a, b), 0, n_);
    }

    // [l, r)
    void add_segment(T l, T r, T a, T b) {
      int left  = std::lower_bound(xs_.begin(), xs_.end(), l) - xs_.begin();
      int right = std::lower_bound(xs_.begin(), xs_.end(), r) - xs_.begin();

      int L = left + n_;
      int R = right + n_;

      while (L < R) {
        if (R & 1) {
          --R;
          update(R, std::make_pair(a, b), range_[R].first, range_[R].second);
        }

        if (L & 1) {
          update(L, std::make_pair(a, b), range_[L].first, range_[L].second);
          ++L;
        }

        L >>= 1;
        R >>= 1;
      }
    }

  public:
    auto operator()(const T &x) const {
      const int i = std::lower_bound(xs_.begin(), xs_.end(), x) - xs_.begin();
      int k       = i + n_;

      std::optional<T> ret;

      while (k > 0) {
        if (data_[k]) {
          if (not ret)
            ret = apply(*data_[k], xs_[i]);
          else
            ret = chm(*ret, apply(*data_[k], xs_[i]));
        }
        k >>= 1;
      }

      return ret;
    }
  };

  template <typename T>
  auto make_lichao_min(const std::vector<T> &xs) {
    return lichao_segment_tree<T, std::less<T>>(xs);
  }

  template <typename T>
  auto make_lichao_max(const std::vector<T> &xs) {
    return lichao_segment_tree<T, std::greater<T>>(xs);
  }
}  // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 6 "Mylib/IO/input_tuple.cpp"

namespace haar_lib {
  template <typename T, size_t... I>
  static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
    (void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
  }

  template <typename T, typename U>
  std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
    s >> value.first >> value.second;
    return s;
  }

  template <typename... Args>
  std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
    input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
    return s;
  }
}  // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"

namespace haar_lib {
  template <typename... Args>
  class InputTuples {
    struct iter {
      using value_type = std::tuple<Args...>;
      value_type value;
      bool fetched = false;
      int N, c = 0;

      value_type operator*() {
        if (not fetched) {
          std::cin >> value;
        }
        return value;
      }

      void operator++() {
        ++c;
        fetched = false;
      }

      bool operator!=(iter &) const {
        return c < N;
      }

      iter(int N) : N(N) {}
    };

    int N;

  public:
    InputTuples(int N) : N(N) {}

    iter begin() const { return iter(N); }
    iter end() const { return iter(N); }
  };

  template <typename... Args>
  auto input_tuples(int N) {
    return InputTuples<Args...>(N);
  }
}  // namespace haar_lib
#line 10 "test/yosupo-judge/segment_add_get_min/main.test.cpp"

namespace hl = haar_lib;

using Segment = std::tuple<int64_t, int64_t, int64_t, int64_t>;
using Query   = std::variant<Segment, int64_t>;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;

  std::vector<int64_t> xs;

  std::vector<Segment> lines;

  for (auto [l, r, a, b] : hl::input_tuples<int64_t, int64_t, int64_t, int64_t>(N)) {
    lines.emplace_back(l, r, a, b);
  }

  std::vector<Query> query;

  for (auto [type] : hl::input_tuples<int>(Q)) {
    switch (type) {
      case 0: {
        int64_t l, r, a, b;
        std::cin >> l >> r >> a >> b;
        query.push_back(Segment({l, r, a, b}));
        break;
      }
      case 1: {
        int64_t p;
        std::cin >> p;
        query.push_back(p);
        xs.push_back(p);
        break;
      }
    }
  }

  if (not xs.empty()) {
    auto lc = hl::make_lichao_min(xs);

    for (auto [l, r, a, b] : lines) {
      lc.add_segment(l, r, a, b);
    }

    for (auto &q : query) {
      if (q.index() == 0) {
        auto [l, r, a, b] = std::get<0>(q);
        lc.add_segment(l, r, a, b);
      } else {
        auto p   = std::get<1>(q);
        auto res = lc(p);

        if (res) {
          std::cout << *res << "\n";
        } else {
          std::cout << "INFINITY"
                    << "\n";
        }
      }
    }
  }

  return 0;
}

Back to top page