sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min" #include <bits/stdc++.h> #include "../../data-structure/cht/li_chao_tree.hpp" using namespace std; using ll = long long; struct Query { int t; ll a, b, p; Query(int t, ll a, ll b) : t(t), a(a), b(b) {} Query(int t, ll p) : t(t), p(p) {} }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N >> Q; vector<pair<ll, ll>> ab(N); for (int i = 0; i < N; ++i) cin >> ab[i].first >> ab[i].second; vector<Query> query; vector<ll> xs; for (int i = 0; i < Q; ++i) { int t; cin >> t; if (t == 0) { ll a, b; cin >> a >> b; query.emplace_back(t, a, b); } else { ll p; cin >> p; query.emplace_back(t, p); xs.push_back(p); } } LiChaoTree<ll> lct(xs); for (auto& p : ab) { lct.add_line(p.first, p.second); } for (auto& q : query) { if (q.t == 0) { lct.add_line(q.a, q.b); } else { cout << lct.get(q.p) << "\n"; } } }
#line 1 "test/yosupo/line_add_get_min.lct.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min" #include <bits/stdc++.h> #line 3 "data-structure/cht/li_chao_tree.hpp" #include <bit> #line 7 "data-structure/cht/li_chao_tree.hpp" template <typename T> class LiChaoTree { public: LiChaoTree() = default; explicit LiChaoTree(const std::vector<T>& vs) : xs(vs) { std::ranges::sort(xs); xs.erase(std::ranges::unique(xs).begin(), xs.end()); size = std::bit_ceil(xs.size()); node.resize(2 * size, {0, INF}); while ((int)xs.size() <= size) xs.push_back(xs.back() + 1); } void add_line(T a, T b) { update({a, b}, 1, 0, size); } void add_segment(T a, T b, T xl, T xr) { int l = std::ranges::lower_bound(xs, xl) - xs.begin(); int r = std::ranges::lower_bound(xs, xr) - xs.begin(); Line line(a, b); int len = 1; int l0 = l, r0 = r; for (l += size, r += size; l < r; l >>= 1, r >>= 1, len <<= 1) { if (l & 1) { update(line, l++, l0, l0 + len); ++l; l0 += len; } if (r & 1) { --r; r0 -= len; update(line, r, r0, r0 + len); } } } T get(T x) const { int k = std::ranges::lower_bound(xs, x) - xs.begin(); k += size; T res = node[k](x); while (k >>= 1) res = std::min(res, node[k](x)); return res; } private: struct Line { T a, b; Line(T a, T b) : a(a), b(b) {} T operator()(T x) const { return a * x + b; } }; static constexpr T INF = std::numeric_limits<T>::max(); int size; std::vector<T> xs; std::vector<Line> node; void update(Line line, int k, int l, int r) { while (true) { int m = std::midpoint(l, r); bool left = line(xs[l]) < node[k](xs[l]); bool mid = line(xs[m]) < node[k](xs[m]); bool right = line(xs[r]) < node[k](xs[r]); if (!left && !right) break; if (left && right) { node[k] = line; break; } if (mid) std::swap(node[k], line); if (r - l == 1) break; if (left != mid) { k = 2 * k; r = m; } else { k = 2 * k + 1; l = m; } } } }; #line 6 "test/yosupo/line_add_get_min.lct.test.cpp" using namespace std; using ll = long long; struct Query { int t; ll a, b, p; Query(int t, ll a, ll b) : t(t), a(a), b(b) {} Query(int t, ll p) : t(t), p(p) {} }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N >> Q; vector<pair<ll, ll>> ab(N); for (int i = 0; i < N; ++i) cin >> ab[i].first >> ab[i].second; vector<Query> query; vector<ll> xs; for (int i = 0; i < Q; ++i) { int t; cin >> t; if (t == 0) { ll a, b; cin >> a >> b; query.emplace_back(t, a, b); } else { ll p; cin >> p; query.emplace_back(t, p); xs.push_back(p); } } LiChaoTree<ll> lct(xs); for (auto& p : ab) { lct.add_line(p.first, p.second); } for (auto& q : query) { if (q.t == 0) { lct.add_line(q.a, q.b); } else { cout << lct.get(q.p) << "\n"; } } }