oj.uz

Submission #708188

# Submission time Handle Problem Language Result Execution time Memory
708188 2023-03-11T09:26:01 Z LittleCube Two Dishes (JOI19_dishes) C++14
49 / 100
 1077 ms 187728 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll inf = 1'000'000'000'000'000'000;
const ll mxN = 3'000'006;
int N, M;
ll A[mxN], B[mxN], S[mxN], T[mxN], P[mxN], Q[mxN], dp[mxN], seg[4 * mxN], lazy[4 * mxN], bit[mxN], rcost[mxN], ucost[mxN], tmp[mxN][2];
int rangeA[mxN], rangeB[mxN], nrange[mxN];
vector<int> ins[mxN];

void Bmodify(int pos, ll val)
{
    for (int i = pos; i < mxN; i += (i & -i))
        bit[i] += val;
}

ll Bquery(int pos)
{
    ll ans = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        ans += bit[i];
    return ans;
}

void init(int i = 1, int L = 0, int R = N)
{
    if (L == R)
        seg[i] = -inf, lazy[i] = 0;
    if (L != R)
    {
        int mid = (L + R) / 2;
        init(i << 1, L, mid);
        init(i << 1 | 1, mid + 1, R);
    }
}

void modify(int mL, int mR, ll val, int i = 1, int L = 0, int R = N)
{
    if (mL <= L && R <= mR)
        seg[i] += val, lazy[i] += val;
    else if (R < mL || mR < L)
        return;
    else
    {
        int mid = (L + R) / 2;
        seg[i << 1] += lazy[i], seg[i << 1 | 1] += lazy[i];
        lazy[i << 1] += lazy[i], lazy[i << 1 | 1] += lazy[i];
        lazy[i] = 0;
        modify(mL, mR, val, i << 1, L, mid);
        modify(mL, mR, val, i << 1 | 1, mid + 1, R);
        seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
    }
}

ll query(int mL, int mR, int i = 1, int L = 0, int R = N)
{
    if (mL <= L && R <= mR)
        return seg[i];
    else if (R < mL || mR < L)
        return -inf;
    else
    {
        int mid = (L + R) / 2;
        seg[i << 1] += lazy[i], seg[i << 1 | 1] += lazy[i];
        lazy[i << 1] += lazy[i], lazy[i << 1 | 1] += lazy[i];
        lazy[i] = 0;
        return max(query(mL, mR, i << 1, L, mid),
                   query(mL, mR, i << 1 | 1, mid + 1, R));
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        cin >> A[i] >> S[i] >> P[i];
        A[i] += A[i - 1];
    }
    for (int i = 1; i <= M; i++)
    {
        cin >> B[i] >> T[i] >> Q[i];
        B[i] += B[i - 1];
    }
    for (int i = 1; i <= N; i++)
    {
        rangeA[i] = upper_bound(B, B + 1 + M, S[i] - A[i]) - B - 1;
        if (rangeA[i] == -1)
            rangeA[i] = 0, P[i] = 0;
    }
    for (int i = 1; i <= M; i++)
    {
        rangeB[i] = upper_bound(A, A + 1 + N, T[i] - B[i]) - A - 1;
        if (rangeB[i] == -1)
            rangeB[i] = 0, Q[i] = 0;
        else if (rangeA[rangeB[i] + 1] >= i)
        {
            // cerr << "build insert " << i << " -> " << rangeB[i] + 1 << '\n';
            ins[rangeB[i] + 1].emplace_back(i - 1);
        }
    }
    rangeA[++N] = M;
    int nN = 0;
    for (int i = 1; i <= N; i++)
        tmp[i][0] = P[i], tmp[i][1] = rangeA[i];
    for (int i = 1; i <= N; i++)
    {
        sort(ins[i].begin(), ins[i].end(), greater<>());
        ++nN;
        P[nN] = 0;
        rangeA[nN] = tmp[i][0] + 1;
        nrange[i] = ++nN;
        P[nN] = tmp[i][0];
        rangeA[nN] = tmp[i][1];
        for (int j : ins[i])
        {
            ++nN;
            rangeA[nN] = j;
            P[nN] = 0;
        }
    }
    for (int i = 1; i <= M; i++)
        rangeB[i] = nrange[rangeB[i]];
    N = nN;
    vector<int> v;

    for (int i = 1; i <= N; i++)
        v.emplace_back(i);
    sort(v.begin(), v.end(), [&](int i, int j)
         { return make_pair(rangeA[i], i) < make_pair(rangeA[j], j); });

    ll sumR = 0;
    for (int i = N; i >= 1; i--)
    {
        rcost[i] = sumR - Bquery(rangeA[i]);
        sumR += P[i];
        Bmodify(rangeA[i] + 1, P[i]);
    }
    for (int i = 0; i < mxN; i++)
        bit[i] = 0;

    int last = 1;
    ll sumU = 0;

    init();
    modify(0, 0, inf);
    for (int i = 1; i <= N; i++)
        modify(0, i, P[i]);
    for (int i : v)
    {
        while (last <= rangeA[i])
        {
            sumU += Q[last];
            Bmodify(rangeB[last] + 1, Q[last]);
            modify(0, rangeB[last], Q[last]);
            last++;
        }
        ucost[i] = sumU - Bquery(i);
        dp[i] = query(0, i - 1) - rcost[i];
        // cerr << ' ' << query(0, 0) << '\n';
        // cerr << i << ' ' << query(0, i - 1) << '-' << rcost[i] << '\n';
        modify(0, i, -P[i]);
        modify(i, i, inf + dp[i] - ucost[i]);
    }
    cout << dp[N] << '\n';
}

/*
2 2
1 1 0
1 2 -1
1 1 0
1 3 -1
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 362 ms 177984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94296 KB Output is correct
2 Correct 48 ms 94360 KB Output is correct
3 Correct 47 ms 94256 KB Output is correct
4 Correct 53 ms 94268 KB Output is correct
5 Correct 49 ms 94284 KB Output is correct
6 Correct 51 ms 94364 KB Output is correct
7 Correct 55 ms 94312 KB Output is correct
8 Correct 51 ms 94284 KB Output is correct
9 Correct 45 ms 94300 KB Output is correct
10 Correct 47 ms 94280 KB Output is correct
11 Correct 45 ms 94344 KB Output is correct
12 Correct 50 ms 94320 KB Output is correct
13 Correct 55 ms 94328 KB Output is correct
14 Correct 60 ms 94344 KB Output is correct
15 Correct 46 ms 94284 KB Output is correct
16 Correct 47 ms 94244 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94296 KB Output is correct
2 Correct 48 ms 94360 KB Output is correct
3 Correct 47 ms 94256 KB Output is correct
4 Correct 53 ms 94268 KB Output is correct
5 Correct 49 ms 94284 KB Output is correct
6 Correct 51 ms 94364 KB Output is correct
7 Correct 55 ms 94312 KB Output is correct
8 Correct 51 ms 94284 KB Output is correct
9 Correct 45 ms 94300 KB Output is correct
10 Correct 47 ms 94280 KB Output is correct
11 Correct 45 ms 94344 KB Output is correct
12 Correct 50 ms 94320 KB Output is correct
13 Correct 55 ms 94328 KB Output is correct
14 Correct 60 ms 94344 KB Output is correct
15 Correct 46 ms 94284 KB Output is correct
16 Correct 47 ms 94244 KB Output is correct
17 Correct 52 ms 94792 KB Output is correct
18 Correct 53 ms 95092 KB Output is correct
19 Correct 55 ms 95100 KB Output is correct
20 Correct 62 ms 94976 KB Output is correct
21 Correct 51 ms 95008 KB Output is correct
22 Correct 53 ms 95028 KB Output is correct
23 Correct 52 ms 94924 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94296 KB Output is correct
2 Correct 48 ms 94360 KB Output is correct
3 Correct 47 ms 94256 KB Output is correct
4 Correct 53 ms 94268 KB Output is correct
5 Correct 49 ms 94284 KB Output is correct
6 Correct 51 ms 94364 KB Output is correct
7 Correct 55 ms 94312 KB Output is correct
8 Correct 51 ms 94284 KB Output is correct
9 Correct 45 ms 94300 KB Output is correct
10 Correct 47 ms 94280 KB Output is correct
11 Correct 45 ms 94344 KB Output is correct
12 Correct 50 ms 94320 KB Output is correct
13 Correct 55 ms 94328 KB Output is correct
14 Correct 60 ms 94344 KB Output is correct
15 Correct 46 ms 94284 KB Output is correct
16 Correct 47 ms 94244 KB Output is correct
17 Correct 52 ms 94792 KB Output is correct
18 Correct 53 ms 95092 KB Output is correct
19 Correct 55 ms 95100 KB Output is correct
20 Correct 62 ms 94976 KB Output is correct
21 Correct 51 ms 95008 KB Output is correct
22 Correct 53 ms 95028 KB Output is correct
23 Correct 52 ms 94924 KB Output is correct
24 Correct 555 ms 145520 KB Output is correct
25 Correct 600 ms 145420 KB Output is correct
26 Correct 578 ms 145764 KB Output is correct
27 Correct 661 ms 152840 KB Output is correct
28 Correct 711 ms 148476 KB Output is correct
29 Correct 562 ms 146576 KB Output is correct
30 Correct 915 ms 152056 KB Output is correct
31 Correct 151 ms 105932 KB Output is correct
32 Correct 441 ms 138216 KB Output is correct
33 Correct 719 ms 146988 KB Output is correct
34 Correct 1077 ms 170048 KB Output is correct
35 Correct 942 ms 149392 KB Output is correct
36 Correct 867 ms 149348 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94296 KB Output is correct
2 Correct 48 ms 94360 KB Output is correct
3 Correct 47 ms 94256 KB Output is correct
4 Correct 53 ms 94268 KB Output is correct
5 Correct 49 ms 94284 KB Output is correct
6 Correct 51 ms 94364 KB Output is correct
7 Correct 55 ms 94312 KB Output is correct
8 Correct 51 ms 94284 KB Output is correct
9 Correct 45 ms 94300 KB Output is correct
10 Correct 47 ms 94280 KB Output is correct
11 Correct 45 ms 94344 KB Output is correct
12 Correct 50 ms 94320 KB Output is correct
13 Correct 55 ms 94328 KB Output is correct
14 Correct 60 ms 94344 KB Output is correct
15 Correct 46 ms 94284 KB Output is correct
16 Correct 47 ms 94244 KB Output is correct
17 Correct 52 ms 94792 KB Output is correct
18 Correct 53 ms 95092 KB Output is correct
19 Correct 55 ms 95100 KB Output is correct
20 Correct 62 ms 94976 KB Output is correct
21 Correct 51 ms 95008 KB Output is correct
22 Correct 53 ms 95028 KB Output is correct
23 Correct 52 ms 94924 KB Output is correct
24 Correct 555 ms 145520 KB Output is correct
25 Correct 600 ms 145420 KB Output is correct
26 Correct 578 ms 145764 KB Output is correct
27 Correct 661 ms 152840 KB Output is correct
28 Correct 711 ms 148476 KB Output is correct
29 Correct 562 ms 146576 KB Output is correct
30 Correct 915 ms 152056 KB Output is correct
31 Correct 151 ms 105932 KB Output is correct
32 Correct 441 ms 138216 KB Output is correct
33 Correct 719 ms 146988 KB Output is correct
34 Correct 1077 ms 170048 KB Output is correct
35 Correct 942 ms 149392 KB Output is correct
36 Correct 867 ms 149348 KB Output is correct
37 Runtime error 313 ms 187728 KB Execution killed with signal 11
38 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94296 KB Output is correct
2 Correct 48 ms 94360 KB Output is correct
3 Correct 47 ms 94256 KB Output is correct
4 Correct 53 ms 94268 KB Output is correct
5 Correct 49 ms 94284 KB Output is correct
6 Correct 51 ms 94364 KB Output is correct
7 Correct 55 ms 94312 KB Output is correct
8 Correct 51 ms 94284 KB Output is correct
9 Correct 45 ms 94300 KB Output is correct
10 Correct 47 ms 94280 KB Output is correct
11 Correct 45 ms 94344 KB Output is correct
12 Correct 50 ms 94320 KB Output is correct
13 Correct 55 ms 94328 KB Output is correct
14 Correct 60 ms 94344 KB Output is correct
15 Correct 46 ms 94284 KB Output is correct
16 Correct 47 ms 94244 KB Output is correct
17 Correct 52 ms 94792 KB Output is correct
18 Correct 53 ms 95092 KB Output is correct
19 Correct 55 ms 95100 KB Output is correct
20 Correct 62 ms 94976 KB Output is correct
21 Correct 51 ms 95008 KB Output is correct
22 Correct 53 ms 95028 KB Output is correct
23 Correct 52 ms 94924 KB Output is correct
24 Correct 555 ms 145520 KB Output is correct
25 Correct 600 ms 145420 KB Output is correct
26 Correct 578 ms 145764 KB Output is correct
27 Correct 661 ms 152840 KB Output is correct
28 Correct 711 ms 148476 KB Output is correct
29 Correct 562 ms 146576 KB Output is correct
30 Correct 915 ms 152056 KB Output is correct
31 Correct 151 ms 105932 KB Output is correct
32 Correct 441 ms 138216 KB Output is correct
33 Correct 719 ms 146988 KB Output is correct
34 Correct 1077 ms 170048 KB Output is correct
35 Correct 942 ms 149392 KB Output is correct
36 Correct 867 ms 149348 KB Output is correct
37 Runtime error 313 ms 187728 KB Execution killed with signal 11
38 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 362 ms 177984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 362 ms 177984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -