sotanishy's code snippets for competitive programming
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"
#include "../../data-structure/cht/convex_hull_trick_binsearchtree.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
ConvexHullTrick<ll> cht;
for (int i = 0; i < N; ++i) {
ll a, b;
cin >> a >> b;
cht.add(a, b);
}
while (Q--) {
int t;
cin >> t;
if (t == 0) {
ll a, b;
cin >> a >> b;
cht.add(a, b);
} else {
int p;
cin >> p;
cout << cht.get(p) << "\n";
}
}
}
#line 1 "test/yosupo/line_add_get_min.cht.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"
#line 2 "data-structure/cht/convex_hull_trick_binsearchtree.hpp"
#include <cassert>
#include <limits>
#include <set>
#include <utility>
template <typename T>
class ConvexHullTrick {
public:
void add(T a, T b) {
a = -a, b = -b;
auto m = lines.insert({a, b, 0});
auto l = m, r = m;
++r;
while (update(m, r)) {
r = lines.erase(r);
}
if (l != lines.begin() && update(--l, m)) {
m = lines.erase(m);
update(l, m);
}
m = l;
while (l != lines.begin() && (--l)->p >= m->p) {
update(l, lines.erase(m));
m = l;
}
}
T get(T x) const {
assert(!lines.empty());
auto it = *lines.lower_bound(x);
return -(it.a * x + it.b);
}
private:
struct Line {
mutable T a, b; // ax + b
mutable double p; // intersection point with the next line
bool operator<(const Line& o) const { return a < o.a; }
bool operator<(T x) const { return p < x; }
};
using iterator = typename std::multiset<Line, std::less<>>::iterator;
static constexpr double INF = std::numeric_limits<double>::max() / 2;
std::multiset<Line, std::less<>> lines;
bool update(iterator x, iterator y) const {
if (y == lines.end()) {
x->p = INF;
return false;
}
if (x->a == y->a) {
x->p = (x->b > y->b ? INF : -INF);
} else {
x->p = 1.0 * (y->b - x->b) / (x->a - y->a);
}
return x->p >= y->p;
}
};
#line 4 "test/yosupo/line_add_get_min.cht.test.cpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
ConvexHullTrick<ll> cht;
for (int i = 0; i < N; ++i) {
ll a, b;
cin >> a >> b;
cht.add(a, b);
}
while (Q--) {
int t;
cin >> t;
if (t == 0) {
ll a, b;
cin >> a >> b;
cht.add(a, b);
} else {
int p;
cin >> p;
cout << cht.get(p) << "\n";
}
}
}