This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min" #include <bits/stdc++.h> using namespace std; #include "../optimizations/dynamic_hull.h" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; HullDynamic hull; REP(i,n) { long long a, b; cin >> a >> b; hull.insert_line(-a, -b); } REP(i,q) { int typ; cin >> typ; if (typ == 0) { long long a, b; cin >> a >> b; hull.insert_line(-a, -b); } else { long long x; cin >> x; cout << -hull.eval(x) << '\n'; } } return 0; }
#line 1 "DP/tests/dynamic_hull_lineaddgetmin.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min" #include <bits/stdc++.h> using namespace std; #line 1 "DP/optimizations/dynamic_hull.h" // source: https://github.com/niklasb/contest-algos/blob/master/convex_hull/dynamic.cpp // Tested: // - https://judge.yosupo.jp/problem/line_add_get_min using ll = long long; const ll INF = (1LL<<62); struct Line { ll m, b; mutable function<const Line*()> succ; bool operator<(const Line& rhs) const { if (rhs.b != -INF) return m < rhs.m; const Line* s = succ(); if (!s) return 0; ll x = rhs.m; return b - s->b < (s->m - m) * x; } }; struct HullDynamic : public multiset<Line> { // will maintain upper hull for maximum bool bad(iterator y) { auto z = next(y); if (y == begin()) { if (z == end()) return 0; return y->m == z->m && y->b <= z->b; } auto x = prev(y); if (z == end()) return y->m == x->m && y->b <= x->b; return 1.0 * (x->b - y->b)*(z->m - y->m) >= 1.0 * (y->b - z->b)*(y->m - x->m); } void insert_line(ll m, ll b) { auto y = insert({ m, b }); y->succ = [=] { return next(y) == end() ? 0 : &*next(y); }; if (bad(y)) { erase(y); return; } while (next(y) != end() && bad(next(y))) erase(next(y)); while (y != begin() && bad(prev(y))) erase(prev(y)); } ll eval(ll x) { auto l = *lower_bound((Line) { x, -INF }); return l.m * x + l.b; } }; #line 7 "DP/tests/dynamic_hull_lineaddgetmin.test.cpp" #define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i) int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; HullDynamic hull; REP(i,n) { long long a, b; cin >> a >> b; hull.insert_line(-a, -b); } REP(i,q) { int typ; cin >> typ; if (typ == 0) { long long a, b; cin >> a >> b; hull.insert_line(-a, -b); } else { long long x; cin >> x; cout << -hull.eval(x) << '\n'; } } return 0; }