Submission #1171010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171010		jerzyk	Two Dishes (JOI19_dishes)	C++20	100 / 100	7383 ms	199048 KiB

dishes

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'00LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<20;
ll tim1[N], tim2[N];
ll sum1[N], sum2[N];
ll lim1[N], lim2[N];
ll cst1[N], cst2[N];

ll sum[2 * N], laz[2 * N];

ll dp[2 * N], laz2[2 * N], claz[2 * N];

vector<int> kon[N];

void Push(int v)
{
    for(int s = v * 2; s <= v * 2 + 1; ++s)
    {
        sum[s] += laz[v];
        laz[s] += laz[v];
    }
    laz[v] = 0LL;
}

void Push2(int v)
{
    for(int s = v * 2; s <= v * 2 + 1; ++s)
    {
        claz[s] += claz[v];
        dp[s] += claz[v];
        laz2[s] += claz[v];
        laz2[s] = max(laz2[s], laz2[v] + laz[s]);
        dp[s] = max(dp[s], laz2[v] + sum[s]);
    }
    laz2[v] = -I;
    claz[v] = 0LL;
}

void Dod(int v, int p, int k, int pz, int kz, ll x)
{
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        sum[v] += x; laz[v] += x;
        return;
    }
    Push2(v);
    Push(v);
    Dod(v * 2, p, (p + k) / 2, pz, kz, x);
    Dod(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
}

void DodDp(int v, int p, int k, int pz, int kz, ll x)
{
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        dp[v] += x; claz[v] += x;
        laz2[v] += x;
        return;
    }
    Push2(v);
    Push(v);
    DodDp(v * 2, p, (p + k) / 2, pz, kz, x);
    DodDp(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
}

void DoFix(int v, int p, int k, int pz, int kz, ll x)
{
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        //cout << "Fix: " << p << " " << k << " " << x << " " << sum[v] << " " << laz[v] << "\n";
        dp[v] = max(dp[v], sum[v] + x);
        laz2[v] = max(laz2[v], x + laz[v]);
        return;
    }
    Push2(v);
    Push(v);
    DoFix(v * 2, p, (p + k) / 2, pz, kz, x);
    DoFix(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
}

void Get(int v)
{
    v += N;
    vector<int> pth;
    v /= 2;
    while(v > 0){pth.pb(v); v /= 2;}
    for(int i = pth.size() - 1; i >= 0; --i)
    {
        Push2(pth[i]);
        Push(pth[i]);
    }
}

void Fix(int p, int m)
{
    Get(p - 1);
    ll cur = dp[N + p - 1] - sum[N + p - 1];
    DoFix(1, 0, N - 1, p, m, cur);
}

inline void E(int i, int m)
{
    for(int j = 0; j < (int)kon[i].size(); ++j)
        Dod(1, 0, N - 1, kon[i][j], m, -cst2[kon[i][j]]);
}

ll DoDP(int n, int m)
{
    dp[N] = 0;
    DoFix(1, 0, N - 1, 1, m, 0LL);
    E(0, m);
    for(int i = 1; i <= n; ++i)
    {
        //cout << "DP: " << i << "\n";
        /*for(int j = 0; j <= m; ++j)
        {
            Get(j);
            cout << dp[j + N] << " ";
        }
        cout << "\n";*/
        //if(i == 1) return 0LL;
        int a = (upper_bound(sum2, sum2 + 1 + m, lim1[i] - sum1[i]) - sum2) - 1;
        //cout << "F1: " << i << " " << a << "\n";
        if(a >= 0)
            DodDp(1, 0, N - 1, 0, a, cst1[i]);

        for(int j = 0; j < (int)kon[i - 1].size(); ++j)
            Fix(kon[i - 1][j], m);
        if(a >= 0)
            Fix(a + 1, m);
        E(i, m);
    }
    Get(m);
    return dp[N + m];
}

void Solve()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        cin >> tim1[i] >> lim1[i] >> cst1[i];
        sum1[i] = (ll)tim1[i] + sum1[i - 1];
    }
    for(int i = 1; i <= m; ++i)
    {
        cin >> tim2[i] >> lim2[i] >> cst2[i];
        sum2[i] = (ll)tim2[i] + sum2[i - 1];
    }
    for(int i = 1; i <= m; ++i)
    {
        int a = (upper_bound(sum1, sum1 + 1 + n, lim2[i] - sum2[i]) - sum1) - 1;
        if(a >= 0)
        {
            Dod(1, 0, N - 1, i, m, cst2[i]);
            kon[a].pb(i);
        }
    }
    ll ans = DoDP(n, m);
    cout << ans << "\n";
}

int main()
{
    for(int i = 1; i < 2 * N; ++i) {laz2[i] = -I; dp[i] = -I;}
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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