The question:

There are n n n weapons per weapon A I a_i ai attack it costs ca I c_{a_i} CAI, m m m armor per defense B I b_i bi costs C b I c_{b_i} cbi, P p p monsters each X x X attack y y Y defend z Z Z gold, choose any weapon choose any armor, kill all monsters that can be killed, the monster that can be killed is your attack is greater than its defense your defense is greater than its attack, Set the initial revenue of the weapon to C A I C_ {a_i} CAI, then enumerate each piece of armor in order of its defense strength to the highest, while constantly updating the armor’s defense strength to be less than the current armor strength, and the answer is the weapon revenue – the maximum cost of the armor. The maintenance of line tree coverage is maximum.

AC code:

const int N = 2e5 + 5;
const int INF = 0x7fffffff;
int n, m, p;

struct node
{
    int a, c;
    node(int x = 0)
    {
        a = x, c = 0;
    }
} wp[N], ar[N];
bool operator<(node a, node b)
{
    return a.a < b.a;
}
struct node2
{
    int x, y, z;
} mon[N];

bool operator<(node2 a, node2 b)
{
    return a.x < b.x;
}

int ans = -INF;
int mx[N << 2], tag[N << 2];

inline void add(int k, int v)
{
    mx[k] += v;
    tag[k] += v;
}
inline void pushup(int k)
{
    mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
}
inline void pushdwn(int k)
{
    add(k << 1, tag[k]);
    add(k << 1 | 1, tag[k]);
    tag[k] = 0;
}
void build(int k, int l, int r)
{
    if (l == r)
    {
        mx[k] = -ar[l].c;
        return;
    }
    int mid = l + r >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    pushup(k);
    return;
}

void modify(int k, int l, int r, int qx, int qy, int qv)
{
    if (qx <= l && r <= qy)
        return add(k, qv);
    pushdwn(k);
    int mid = l + r >> 1;
    if (qx <= mid)
        modify(k << 1, l, mid, qx, qy, qv);
    if (mid < qy)
        modify(k << 1 | 1, mid + 1, r, qx, qy, qv);
    pushup(k);
    return;
}

int main(a)
{
    sddd(n, m, p);
    rep(i, 1, n)
        sdd(wp[i].a, wp[i].c);
    rep(i, 1, m)
        sdd(ar[i].a, ar[i].c);
    sort(wp + 1, wp + n + 1);
    sort(ar + 1, ar + m + 1);
    rep(i, 1, p)
        sddd(mon[i].x, mon[i].y, mon[i].z);
    sort(mon + 1, mon + p + 1);
    build(1.1, m);
    for (int i = 1, s1 = 0; i <= n; i++)
    {
        while (s1 < p && mon[s1 + 1].x < wp[i].a)
        {
            s1++;
            int w = upper_bound(ar + 1, ar + m + 1.node(mon[s1].y)) - ar;
            if (w <= m)
                modify(1.1, m, w, m, mon[s1].z);
        }
        ans = max(ans, mx[1] - wp[i].c);
    }
    pd(ans);
    return 0;
}
Copy the code