Untitled

struct Result
{
    int mPrice;
    int mPerformance;
};
#include <iostream>
const int inf = 1e8;
int cnt[2][3];
const int maxn = 1e5 + 50;
int rt[2][3];
struct segment
{
    struct node
    {
        int l, r, mi;
    }tr[maxn<<2];
    int ncnt;
    static int M;
    void init()
    {
        ncnt = 0;
        for (M = 1; M < (int)1e6; M<<=1);
        tr[0].mi = inf;
    }
    int newnode()
    {
        ++ncnt;
        tr[ncnt].l = tr[ncnt].r = 0;
        tr[ncnt].mi = inf;
        return ncnt;
    }
    void update(int p, int x, int &now, int pl = 1, int pr = M)
    {
        if (!now) now = newnode();
        if (pl == pr)
        {
            tr[now].mi = std::min(tr[now].mi, x);
            return;
        }
        int mid = (pl + pr)>>1;
        if (mid >= p) update(p, x, tr[now].l, pl, mid);
        else update(p, x, tr[now].r, mid + 1, pr);
        tr[now].mi = std::min(tr[tr[now].l].mi, tr[tr[now].r].mi);
    }
    int query(int p, int now, int pl = 1, int pr = M)
    {
        if (!now) return inf;
        if (pl >= p) return tr[now].mi;
        int mid = (pl + pr)>>1;
        int ret = inf;
        if (mid >= p) ret = std::min(ret, query(p, tr[now].l, pl, mid));
        ret = std::min(ret, query(p, tr[now].r, mid + 1, pr));
        return ret;
    }
}seg[2][3];
int segment::M = 0;
 
int shipCharge;
void init(int mCharge)
{
    shipCharge = mCharge;
    for(int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) cnt[i][j] = rt[i][j] = 0, seg[i][j].init();
}
 
int stock(int mType, int mPrice, int mPerformance, int mPosition)
{
    seg[mPosition][mType].update(mPerformance, mPrice, rt[mPosition][mType]);
    return ++cnt[mPosition][mType];
}
 
int price[2][3];
int check(int x, int mBudget)
{
    int ans = inf;
    for (int p = 0; p < 2; p++)
    {
        price[p][0] = price[p][1] = price[p][2] = inf;
        for (int j = 0; j < 3; j++)
        {
            price[p][j] = seg[p][j].query(x, rt[p][j]);
        }
    }
    ans = std::min(ans, std::min(price[0][0], price[1][0]) + std::min(price[0][1], price[1][1]) + std::min(price[0][2], price[1][2]) + shipCharge);
    ans = std::min(ans, price[0][0] + price[0][1] + price[0][2]);
    ans = std::min(ans, price[1][0] + price[1][1] + price[1][2]);
    return ans > mBudget ? -1 : ans;
}
 
Result order(int mBudget)
{
    Result res = { 0, 0 };
    int l = 0, r = 1000000 + 50;
    int ret = 0;
    while(l < r)
    {
        int mid = (l + r + 1)>>1;
        if (-1 != (ret = check(mid, mBudget)))
        {
            l = mid;
            res.mPrice = ret;
            res.mPerformance = mid;
        }
        else r = mid - 1;
    }
    if (l == 0) return {0, 0};
    return res;
}