test/data-structure/LineContainer.test.cpp

• View this file on GitHub
• Last update: 2026-07-28 02:25:06+09:00
• Problem: https://judge.yosupo.jp/problem/line_add_get_min

Depends on

• Line Container (CHT) (src/data-structure/LineContainer.hpp)
• test/template.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/line_add_get_min
#include "test/template.hpp"
#include "src/data-structure/LineContainer.hpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);

   ll N, Q;
   cin >> N >> Q;

   LineContainer cht;
   auto add = [&](ll a, ll b) { cht.add(-a, -b); };

   rep(i, 0, N) {
      ll a, b;
      cin >> a >> b;
      add(a, b);
   }

   while(Q--) {
      ll t;
      cin >> t;
      if(t == 0) {
         ll a, b;
         cin >> a >> b;
         add(a, b);
      } else {
         ll x;
         cin >> x;
         cout << -cht.max(x) << '\n';
      }
   }
}

#line 1 "test/data-structure/LineContainer.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/line_add_get_min
#line 1 "test/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
template<class T> using V = vector<T>;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define each(i, a) for(auto&& i : a)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#line 1 "src/data-structure/LineContainer.hpp"
struct Line {
   mutable ll a, b, p;
   bool operator<(Line o) const { return a < o.a; }
   bool operator<(ll x) const { return p < x; }
};
// for doubles, use INFINITY and div(a,b) = a/b
struct LineContainer : set<Line, less<>> {
   // floored division (b > 0)
   ll div(ll a, ll b) { return a / b - (a % b < 0); }
   bool check(auto x, auto y) {
      x->p = div(x->b - y->b, y->a - x->a);
      return x->p >= y->p;
   }
   void add(ll a, ll b) {  // add line ax + b
      auto [z, f] = emplace(a, b, LLONG_MAX);
      chmax(z->b, b);
      auto y = z++, x = y;
      while(z != end() && check(y, z)) z = erase(z);
      if(x != begin() && check(--x, y)) check(x, y = erase(y));
      while((y = x) != begin() && (--x)->p >= y->p) check(x, erase(y));
   }
   ll max(ll x) {
      assert(size());
      auto l = *lower_bound(x);
      return l.a * x + l.b;
   }
};
#line 4 "test/data-structure/LineContainer.test.cpp"

int main() {
   cin.tie(0)->sync_with_stdio(0);

   ll N, Q;
   cin >> N >> Q;

   LineContainer cht;
   auto add = [&](ll a, ll b) { cht.add(-a, -b); };

   rep(i, 0, N) {
      ll a, b;
      cin >> a >> b;
      add(a, b);
   }

   while(Q--) {
      ll t;
      cin >> t;
      if(t == 0) {
         ll a, b;
         cin >> a >> b;
         add(a, b);
      } else {
         ll x;
         cin >> x;
         cout << -cht.max(x) << '\n';
      }
   }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	3 ms	4 MB
g++	half_00	AC	54 ms	4 MB
g++	hand_max_00	AC	212 ms	16 MB
g++	max_random_00	AC	88 ms	4 MB
g++	max_random_01	AC	86 ms	4 MB
g++	max_random_02	AC	86 ms	4 MB
g++	no_output_00	AC	92 ms	4 MB
g++	parabola_random_00	AC	174 ms	16 MB
g++	parabola_random_01	AC	177 ms	16 MB
g++	parabola_random_02	AC	177 ms	16 MB
g++	random_00	AC	62 ms	4 MB
g++	random_01	AC	68 ms	4 MB
g++	random_02	AC	40 ms	4 MB
g++	small_00	AC	2 ms	4 MB
g++	small_01	AC	2 ms	4 MB

Back to top page