Untitled

#include <cstdio>
  
struct Result {
    int mPrice;
    int mPerformance;
};
  
long long seed;
int nextRand() {
    seed = seed * 134775813 + 1;
    return ((seed >> 33) & 0x7FFFFFFFLL) % 1000000007;
}
  
struct Node;
using Ptr = Node*;
  
struct Node {
    Ptr le;
    Ptr ri;
    int si;
    int we;
  
    int perf;
    int cost;
    int min;
};
  
const int N = 4000 + 9;
const int MAXINT = 0x07FFFFFF;
Node nodeArr[N];
Node* null;
int nextNode;
Ptr  newNode(int p, int c) {
    ++nextNode;
    nodeArr[nextNode] = { null, null, 1, nextRand(), p, c, c };
    return nodeArr + nextNode;
}
  
int myMin(int a, int b) { return a < b ? a : b; }
int myMin(int a, int b, int c) { return a < b ? (a < c ? a : c) : (b < c ? b : c); }
  
int trSize(Ptr node) { return node == null ? 0 : node->si; }
  
Ptr trSetLeft(Ptr node, Ptr son) {
    node->le = son;
    node->si = node->le->si + 1 + node->ri->si;
    node->min = myMin(node->le->min, node->cost, node->ri->min);
    return node;
}
Ptr trSetRight(Ptr node, Ptr son) {
    node->ri = son;
    node->si = node->le->si + 1 + node->ri->si;
    node->min = myMin(node->le->min, node->cost, node->ri->min);
    return node;
}
  
Ptr trMerge(Ptr a, Ptr b) {
    if (a == null) return b;
    if (b == null) return a;
    if (a->we >= b->we) {
        Ptr tmp = trMerge(a->ri, b);
        return trSetRight(a, tmp);
    }
    Ptr tmp = trMerge(a, b->le);
    return trSetLeft(b, tmp);
}
  
Ptr trInsert(Ptr node, int p, int c) {
    if (node == null) return newNode(p, c);
    if (p < node->perf) {
        Ptr tmp = trInsert(node->le, p, c);
        trSetLeft(node, null);
        return trMerge(tmp, node);
    }
    Ptr tmp = trInsert(node->ri, p, c);
    trSetRight(node, null);
    return trMerge(node, tmp);
}
  
int trMinCostRight(Ptr node, int p) {
    if (node == null) return MAXINT;
    if (node->perf < p) return trMinCostRight(node->ri, p);
    return myMin(trMinCostRight(node->le, p), node->cost, node->ri->min);
}
  
int add;
Ptr root[2][3];
int extra[2][3];
  
void init(int mCharge) {
    null = nodeArr;
    nextNode = 0;
    nodeArr[0] = { null, null, 0, -1, 0, MAXINT, MAXINT };
    add = mCharge;
    for (int i = 0; i < 2; ++i) for (int j = 0; j < 3; ++j) {
        root[i][j] = null;
        extra[i][j] = 0;
    }
}
  
int stock(int mType, int mPrice, int mPerformance, int mPosition) {
    Ptr& r = root[mPosition][mType];
    int &ex = extra[mPosition][mType];
    if (trMinCostRight(r, mPerformance) > mPrice) {
        r = trInsert(r, mPerformance, mPrice);
    } else {
        //fprintf(stderr, "skip: %d/%d %d %d\n", mPosition, mType, mPerformance, mPrice);
        ++ex;
    }
    return trSize(r) + ex;
}
  
int bestCost(int perf) {
    int cost[2][3];
    for (int i = 0; i < 2; ++i) for (int j = 0; j < 3; ++j)
        cost[i][j] = trMinCostRight(root[i][j], perf);
    int res = MAXINT;
    res = myMin(res, cost[0][0] + cost[0][1] + cost[0][2]);
    res = myMin(res, cost[0][0] + cost[0][1] + cost[1][2] + add);
    res = myMin(res, cost[0][0] + cost[1][1] + cost[0][2] + add);
    res = myMin(res, cost[0][0] + cost[1][1] + cost[1][2] + add);
    res = myMin(res, cost[1][0] + cost[0][1] + cost[0][2] + add);
    res = myMin(res, cost[1][0] + cost[0][1] + cost[1][2] + add);
    res = myMin(res, cost[1][0] + cost[1][1] + cost[0][2] + add);
    res = myMin(res, cost[1][0] + cost[1][1] + cost[1][2]);
    return res;
}
  
Result order(int mBudget) {
    int a = 0;
    int b = 1000000 + 1;
    int bc = 0;
    while (a + 1 < b) {
        int mid = (a + b) / 2;
        int cost = bestCost(mid);
        if (cost > mBudget) {
            b = mid;
        } else {
            a = mid;
            bc = cost;
        }
    }
    return { bc, a };
}