test/yosupo/line_add_get_min.CHT.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://judge.yosupo.jp/problem/line_add_get_min

Depends on

• Convex-Hull-Trick (src/Optimization/ConvexHullTrick.hpp)
• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/line_add_get_min
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include "src/Optimization/ConvexHullTrick.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 ConvexHullTrick<long long, MINIMIZE> cht;
 for (int i= 0; i < N; ++i) {
  long long a, b;
  cin >> a >> b;
  cht.insert(a, b);
 }
 while (Q--) {
  int t;
  cin >> t;
  if (t) {
   int p;
   cin >> p;
   cout << cht.query(p) << '\n';
  } else {
   long long a, b;
   cin >> a >> b;
   cht.insert(a, b);
  }
 }
 return 0;
}

#line 1 "test/yosupo/line_add_get_min.CHT.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/line_add_get_min
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#line 2 "src/Optimization/ConvexHullTrick.hpp"
#include <limits>
#include <algorithm>
#include <set>
#include <array>
#include <cassert>
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 8 "src/Optimization/ConvexHullTrick.hpp"
template <typename T, MinMaxEnum obj= MINIMIZE> class ConvexHullTrick {
 struct Line {
  T k, m;
  mutable T p;
  bool operator<(const Line &o) const { return k < o.k; }
  bool operator<(T x) const { return p < x; }
 };
 static constexpr T INF= std::numeric_limits<T>::max();
 static T lc_div(T a, T b) {
  if constexpr (std::is_integral_v<T>) return a / b - ((a ^ b) < 0 && a % b);
  else return a / b;
 }
 using ms= std::multiset<Line, std::less<>>;
 ms ls;
 bool insect(typename ms::iterator x, typename ms::iterator y) {
  if (y == ls.end()) return x->p= INF, false;
  if (x->k == y->k) x->p= (x->m > y->m ? INF : -INF);
  else x->p= lc_div(y->m - x->m, x->k - y->k);
  return x->p >= y->p;
 }
public:
 void insert(T k, T m) {
  if constexpr (obj == MINIMIZE) k= -k, m= -m;
  auto z= ls.insert({k, m, 0}), y= z++, x= y;
  while (insect(y, z)) z= ls.erase(z);
  if (x != ls.begin() && insect(--x, y)) insect(x, y= ls.erase(y));
  while ((y= x) != ls.begin() && (--x)->p >= y->p) insect(x, ls.erase(y));
 }
 bool empty() const { return ls.empty(); }
 std::array<T, 2> query_line(T x) const {
  assert(!ls.empty());
  auto l= ls.lower_bound(x);
  if constexpr (obj == MINIMIZE) return {-l->k, -l->m};
  else return {l->k, l->m};
 }
 T query(T x) const {
  auto [k, m]= query_line(x);
  return k * x + m;
 }
};
template <typename T> class ConvexHullTrick_XY {
 ConvexHullTrick<long double, MINIMIZE> cht_mn;
 ConvexHullTrick<long double, MAXIMIZE> cht_mx;
 T amx= std::numeric_limits<T>::lowest(), amn= std::numeric_limits<T>::max();
public:
 void insert(T a, T b) { cht_mn.insert(a, b), cht_mx.insert(a, b), amn= std::min(amn, a), amx= std::max(amx, a); }
 bool empty() const { return cht_mn.empty(); }
 T get_max(T x, T y) const {
  assert(!cht_mn.empty());
  if (y == 0) return std::max(amn * x, amx * x);
  auto z= (long double)x / y;
  auto [a, b]= y > 0 ? cht_mx.query_line(z) : cht_mn.query_line(z);
  return T(a) * x + T(b) * y;
 }
 T get_min(T x, T y) const {
  assert(!cht_mn.empty());
  if (y == 0) return std::min(amn * x, amx * x);
  auto z= (long double)x / y;
  auto [a, b]= y > 0 ? cht_mn.query_line(z) : cht_mx.query_line(z);
  return T(a) * x + T(b) * y;
 }
};
#line 6 "test/yosupo/line_add_get_min.CHT.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 ConvexHullTrick<long long, MINIMIZE> cht;
 for (int i= 0; i < N; ++i) {
  long long a, b;
  cin >> a >> b;
  cht.insert(a, b);
 }
 while (Q--) {
  int t;
  cin >> t;
  if (t) {
   int p;
   cin >> p;
   cout << cht.query(p) << '\n';
  } else {
   long long a, b;
   cin >> a >> b;
   cht.insert(a, b);
  }
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	example_00	AC	5 ms	4 MB
g++-13	half_00	AC	55 ms	4 MB
g++-13	hand_max_00	AC	176 ms	16 MB
g++-13	max_random_00	AC	93 ms	4 MB
g++-13	max_random_01	AC	95 ms	4 MB
g++-13	max_random_02	AC	92 ms	4 MB
g++-13	no_output_00	AC	96 ms	4 MB
g++-13	parabola_random_00	AC	164 ms	16 MB
g++-13	parabola_random_01	AC	161 ms	16 MB
g++-13	parabola_random_02	AC	164 ms	16 MB
g++-13	random_00	AC	67 ms	4 MB
g++-13	random_01	AC	70 ms	4 MB
g++-13	random_02	AC	46 ms	4 MB
g++-13	small_00	AC	6 ms	4 MB
g++-13	small_01	AC	5 ms	4 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	half_00	AC	56 ms	4 MB
clang++-18	hand_max_00	AC	190 ms	16 MB
clang++-18	max_random_00	AC	93 ms	4 MB
clang++-18	max_random_01	AC	93 ms	4 MB
clang++-18	max_random_02	AC	92 ms	4 MB
clang++-18	no_output_00	AC	96 ms	3 MB
clang++-18	parabola_random_00	AC	167 ms	16 MB
clang++-18	parabola_random_01	AC	176 ms	16 MB
clang++-18	parabola_random_02	AC	174 ms	16 MB
clang++-18	random_00	AC	68 ms	4 MB
clang++-18	random_01	AC	70 ms	4 MB
clang++-18	random_02	AC	43 ms	4 MB
clang++-18	small_00	AC	5 ms	4 MB
clang++-18	small_01	AC	5 ms	4 MB

Back to top page