Convex hull trick max

#include <bits/stdc++.h>
#define endl '\n'

#define int long long
#define double long double

using namespace std;
const int MAXN = (1 << 20);
const int inf = (int)1e17 + 42;

struct convex_hull_trick
{
    struct line
    {
        int m, b, is_query;
        double line_x, val;

        line() {m = 0; b = 0; is_query = 0; line_x = 0; val = 0;}
        line(int _m, int _b) {m = _m; b = _b; is_query = 0; line_x = 0; val = 0;}

        bool operator<(const line &l2) const
        {
            if(!is_query && !l2.is_query) return m < l2.m;
            else if(l2.is_query) return line_x < l2.val;
            else return val < l2.line_x;
        }

        int value_at(int x) const
        {
            return m * x + b;
        }
    };

    set<line> hull;
    void clear() { hull.clear(); }
    void init() { clear(); }

    bool parallel(const line &l1, const line &l2) { return l1.m == l2.m; }

    double intersect_x(const line &l1, const line &l2)
    {
        if(parallel(l1, l2)) return inf;
        return (double)(l1.b - l2.b) / (double)(l2.m - l1.m);
    }

    bool has_prev(set<line>::iterator it) {return it != hull.end() && it != hull.begin();}
    bool has_next(set<line>::iterator it) {return it != hull.end() && next(it) != hull.end();}

    bool irrelevant(const line &l1, const line &l2, const line &l3) { return intersect_x(l1, l3) <= intersect_x(l1, l2); }
    bool irrelevant(set<line>::iterator it) { return has_prev(it) && has_next(it) && irrelevant(*prev(it), *it, *next(it)); }

    set<line>::iterator update_border(set<line>::iterator it)
    {
        double val;
        if(!has_next(it)) val = inf;
        else val = intersect_x(*it, *next(it));

        line tmp(*it);
        tmp.line_x = val;
        it = hull.erase(it);
        it = hull.insert(it, tmp);
        return it;
    }

    void add_line(int m, int b)
    {
        line to_add = line(m, b);
        set<line>::iterator it = hull.lower_bound(to_add);

        if(it != hull.end() && parallel(to_add, *it))
        {
            if(it->b < b) it = hull.erase(it);
            else return;
        }

        it = hull.insert(it, to_add);
        if(irrelevant(it)) {it = hull.erase(it); return; }

        while(has_prev(it) && irrelevant(prev(it))) hull.erase(prev(it));
        while(has_next(it) && irrelevant(next(it))) hull.erase(next(it));

        it = update_border(it);
        if(has_prev(it)) update_border(prev(it));
        if(has_next(it)) update_border(next(it));
    }

    int query(int x)
    {
        line to_find;
        to_find.is_query = 1;
        to_find.val = x;

        set<line>::iterator best_line = hull.lower_bound(to_find);
        if(best_line == hull.end())
            return inf;

        return best_line->value_at(x);
    }
};

void read()
{

}

convex_hull_trick cht;

void solve()
{
    cht.init();
}

#undef int
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    read();
    solve();
    return 0;
}