Convex Hull Trick Dp optimization

vector<ll>tangent,con;int type;

bool bad(int f1,int f2,int f3){
    if(type==1||type==4){
        return 1.0*(con[f3]-con[f1])*(tangent[f1]-tangent[f2]) <= 1.0*(con[f2]-con[f1])*(tangent[f1]-tangent[f3]);
    }
    else {
        return 1.0*(con[f3]-con[f1])*(tangent[f1]-tangent[f2]) >= 1.0*(con[f2]-con[f1])*(tangent[f1]-tangent[f3]);
    }
}

void add(ll a,ll b){
    tangent.pb(a);
    con.pb(b);
    int sz = tangent.size();
    while(sz>=3&&bad(sz-3,sz-2,sz-1)){
        tangent.erase(tangent.end()-2);
        con.erase(con.end()-2);
        sz --;
    }
}

ll getval(int indx,ll x){
    return tangent[indx]*x + con[indx];
}

ll query1(ll x){
    int low = 0,high = tangent.size() - 1;
    int save;
    ll ans = 1e18;
    while(low<=high){
        ll diff = high - low;
        ll mid1 = low + diff / 3,mid2 = high - (diff) / 3;
        ll x1 = getval(mid1,x) , x2 = getval(mid2,x);
        if(x1<=x2){
            high = mid2-1;
            if(ans>x1){
                ans = x1;
                save = mid1;
            }
        }
        else {
            low = mid1+1;
            if(x2<ans){
                ans = x2;
                save = mid2;
            }
        }
    }
    return getval(save,x);
}

ll query2(ll x){
    int low = 0,high = tangent.size() - 1;
    int save;
    ll ans = -1e18;
    while(low<=high){
        ll diff = high - low;
        ll mid1 = low + diff / 3,mid2 = high - (diff) / 3;
        ll x1 = getval(mid1,x) , x2 = getval(mid2,x);
        if(x1<x2){
            low = mid1+1;
            if(x2>ans){
                ans = x2;
                save = mid2;
            }
        }
        else {
            high = mid2-1;
            if(x1>ans){
                ans = x1;
                save = mid1;
            }
        }
    }
    return getval(save,x);
}

int main()
{
    booster()
   // read("input.txt");
    int q;
    cin >> q >> type;

    while(q--){
        int t;
        cin >> t;
        if(t==1){
            ll m,b;
            cin >> m >> b;
            add(m,b);
        }
        else {
            ll x;
            cin >> x;
            if(type==1 || type == 3){
                cout << query1(x) ;
            }
            else {
                cout << query2(x);
            }
            cout << endl;
        }
    }

    return 0;
}