제출 #1276565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276565		tvgk	Two Dishes (JOI19_dishes)	C++20	69 / 100	2873 ms	92744 KiB

dishes

#include<bits/stdc++.h>
using namespace std;
#define task "aa"
#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();
//    freopen(task".INP", "r", stdin);
//    freopen(task".OUT", "w", stdout);

    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]);

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

        Upd(j + 1, n[1], Get(j), 0);
    }
    cout << tree[1] + sum;
}

• Subtask 1: 0 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9