DP/tests/dynamic_hull_lineaddgetmin.test.cpp

• View this file on GitHub
• Last update: 2022-12-26 18:09:30+08:00
• Problem: https://judge.yosupo.jp/problem/line_add_get_min

Depends on

• DP/optimizations/dynamic_hull.h

Code

#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;
}

Back to top page