Li‐Chao - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e6 + 5;

struct Line {
    ll m = 0, b = 0;

    Line(ll m, ll b) : m(m), b(b) {}

    ll operator()(ll x) {
        return m * x + b;
    }
};

struct node {
    node *left, *right;
    Line line;

    node(node *left, node *right, Line line) : left(left), right(right), line(line) {}

    node *getLeft() {
        if (left == NULL)
            left = new node(NULL, NULL, Line(0, 1e18));
        return left;
    }

    node *getright() {
        if (right == NULL)
            right = new node(NULL, NULL, Line(0, 1e18));
        return right;
    }
};

node *insert(node *root, Line newline, ll l = -N, ll r = N) {

    node *cur = new node(root->getLeft(), root->getright(), root->line);
    ll m = (l + r) / 2;
    bool lef = newline(l) < cur->line(l);
    bool mid = newline(m) < cur->line(m);

    if (mid)
        swap(cur->line, newline);
    if (r - l == 1)
        return cur;
    else if (lef != mid)
        cur->left = insert(root->getLeft(), newline, l, m);
    else
        cur->right = insert(root->getright(), newline, m, r);

    return cur;
}

ll query(node *cur, ll x, ll l = -N, ll r = N) {
    if (cur == NULL)return 1e18;

    ll m = (l + r) / 2;
    if (r - l == 1)
        return cur->line(x);
    else if (x < m)
        return min(cur->line(x), query(cur->left, x, l, m));
    else
        return min(cur->line(x), query(cur->right, x, m, r));
}

node *dp[N];

int main() {
    dp[0] = new node(NULL, NULL, Line(0, 1e18)); // change to -1e18 if max 
    dp[1] = insert(dp[0], Line(2,1));
    cout << query(dp[1], -10); // -19
}