제출 #1276550

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

dishes

#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], lazy[mxN * 4];

void Down(int j)
{
    for (int i = 0; i <= 1; i++)
    {
        tree[j * 2 + i] += lazy[j];
        lazy[j * 2 + i] += lazy[j];
    }
    lazy[j] = 0;
}

void Upd_rt(int vt, ll nw, int j = 1, int l = 0, int r = n[1])
{
    if (l > vt || vt > r)
        return;

    if (l == r)
    {
        tree[j] = max(nw, tree[j]);
        return;
    }
    Down(j);

    int mid = (l + r) / 2;
    Upd_rt(vt, nw, j * 2, l, mid);
    Upd_rt(vt, nw, j * 2 + 1, mid + 1, r);
    tree[j] = max(tree[j * 2], tree[j * 2 + 1]);
}

void Upd(int u, int v, 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] += inc;
        tree[j] += inc;
        return;
    }
    Down(j);

    int mid = (l + r) / 2;
    Upd(u, v, inc, j * 2, l, mid);
    Upd(u, v, 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++)
    {
        while (ctr <= n[1] && lim[stt[ctr]][1] < pre[0][i])
        {
            Upd(stt[ctr], n[1], point[stt[ctr]][1]);
            sum -= point[stt[ctr]][1];
            ctr++;
        }

        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_rt(j + 1, Get(j));
        Upd(0, j, point[i][0]);
    }
    cout << tree[1] + sum;
}

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