Submission #1276570

#TimeUsernameProblemLanguageResultExecution timeMemory
1276570tvgkTwo Dishes (JOI19_dishes)C++20
74 / 100
3262 ms92888 KiB
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 1e6 + 7;
const ll inf = 1e18;

int n[2], point[mxN][2], stt[mxN];
ll lim[mxN][2], pre[2][mxN], tree[mxN * 4];
ii lazy[mxN * 4];

void Down(int j)
{
    for (int i = 0; i <= 1; i++)
    {
        tree[j * 2 + i] = max(lazy[j].fi, tree[j * 2 + i] + lazy[j].se);
        lazy[j * 2 + i].fi = max(lazy[j].fi, lazy[j * 2 + i].fi + lazy[j].se);
        lazy[j * 2 + i].se += lazy[j].se;
    }
    lazy[j] = {-inf, 0};
}

void Upd(int u, int v, ll bf, ll inc, int j = 1, int l = 0, int r = n[1])
{
    if (u > r || l > v)
        return;

    if (u <= l && r <= v)
    {
        lazy[j].fi = max(lazy[j].fi + inc, bf);
        lazy[j].se += inc;
        tree[j] = max(tree[j] + inc, bf);
        return;
    }
    Down(j);

    int mid = (l + r) / 2;
    Upd(u, v, bf, inc, j * 2, l, mid);
    Upd(u, v, bf, inc, j * 2 + 1, mid + 1, r);
    tree[j] = max(tree[j * 2], tree[j * 2 + 1]);
}

ll Get(int vt, int j = 1, int l = 0, int r = n[1])
{
    if (l > vt)
        return -inf;

    if (r <= vt)
        return tree[j];
    Down(j);

    int mid = (l + r) / 2;
    return max(Get(vt, j * 2, l, mid), Get(vt, j * 2 + 1, mid + 1, r));
}

bool cmp(int u, int v)
{
    return lim[u][1] < lim[v][1];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    cin >> n[0] >> n[1];
    ll sum = 0;
    for (int k = 0; k <= 1; k++)
    {
        sum = 0;
        for (int i = 1; i <= n[k]; i++)
        {
            int tmp;
            cin >> tmp >> lim[i][k] >> point[i][k];
            pre[k][i] = pre[k][i - 1] + tmp;
            lim[i][k] -= pre[k][i];
            stt[i] = i;
            sum += point[i][k] * (lim[i][k] >= 0);
        }
    }
    sort(stt + 1, stt + n[1] + 1, cmp);

    int ctr = 1;
    while (ctr <= n[1] && lim[stt[ctr]][1] < 0)
        ctr++;

    for (int i = 1; i <= n[0]; i++)
    {
        if (lim[i][0] < 0)
            continue;

        int j = upper_bound(pre[1] + 1, pre[1] + n[1] + 1, lim[i][0]) - pre[1] - 1;
        Upd(0, j, -inf, point[i][0]);

        vector<int> mem;
        mem.push_back(j);

        while (ctr <= n[1] && lim[stt[ctr]][1] < pre[0][i])
        {
            mem.push_back(stt[ctr] - 1);
            Upd(stt[ctr], n[1], -inf, point[stt[ctr]][1]);
            sum -= point[stt[ctr]][1];
            ctr++;
        }

        for (int j : mem)
            Upd(j + 1, n[1], Get(j), 0);
    }
    cout << tree[1] + sum;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...