oj.uz

Submission #708237

# Submission time Handle Problem Language Result Execution time Memory
708237 2023-03-11T11:15:49 Z LittleCube Two Dishes (JOI19_dishes) C++14
74 / 100
 5130 ms 301004 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 = 2'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 - 1 && rangeB[i] < N)
        {
            // cerr << "build insert " << i << " -> " << rangeB[i] + 1 << '\n';
            ins[rangeB[i] + 1].emplace_back(i - 1);
        }
    }
    rangeA[++N] = M;
    for (int i = 1; i <= N; i++)
        ins[i].emplace_back(rangeA[i]);
    for (int i = 1; i <= N; i++)
        tmp[i][0] = P[i], tmp[i][1] = rangeA[i];
    int nN = 0;
    for (int i = 1; i <= N; i++)
    {
        sort(ins[i].begin(), ins[i].end(), greater<>());
        for (int j : ins[i])
        {
            ++nN;
            rangeA[nN] = j;
            P[nN] = 0;
            if (j == tmp[i][1])
            {
                P[nN] = tmp[i][0];
                rangeA[nN] = tmp[i][1];
                nrange[i] = nN;
            }
        }
    }
    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] + 1);
        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 - 1, P[i]);
    for (int i : v)
    {
        while (last <= rangeA[i] && last <= M)
        {
            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 << i << ' ' << rangeA[i] << ' ' << query(0, i - 1) << " - " << rcost[i] << '\n';
        modify(0, i - 1, -P[i]);
        modify(i, i, inf + dp[i] - ucost[i]);
    }
    cout << dp[N] << '\n';
}

/*
1 2
1 0 0
1 0 0
1 5 -1

3 3
1 1 1
1 3 -5
1 4 -2
1 1 2
1 3 -1
1 4 -2

2 2
1 1 5
1 10 -10
1 0 0
1 3 6

2 2
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 101372 KB Output is correct
2 Correct 443 ms 100632 KB Output is correct
3 Correct 367 ms 99772 KB Output is correct
4 Correct 414 ms 99308 KB Output is correct
5 Correct 39 ms 63040 KB Output is correct
6 Correct 424 ms 100788 KB Output is correct
7 Correct 125 ms 70348 KB Output is correct
8 Correct 264 ms 94496 KB Output is correct
9 Correct 376 ms 99800 KB Output is correct
10 Correct 371 ms 99884 KB Output is correct
11 Correct 314 ms 99724 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63012 KB Output is correct
2 Correct 32 ms 63040 KB Output is correct
3 Correct 35 ms 63068 KB Output is correct
4 Correct 34 ms 62972 KB Output is correct
5 Correct 34 ms 62944 KB Output is correct
6 Correct 32 ms 62984 KB Output is correct
7 Correct 32 ms 63060 KB Output is correct
8 Correct 35 ms 62956 KB Output is correct
9 Correct 35 ms 63052 KB Output is correct
10 Correct 33 ms 63040 KB Output is correct
11 Correct 32 ms 62992 KB Output is correct
12 Correct 38 ms 63052 KB Output is correct
13 Correct 34 ms 63044 KB Output is correct
14 Correct 38 ms 63040 KB Output is correct
15 Correct 35 ms 62972 KB Output is correct
16 Correct 40 ms 63032 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63012 KB Output is correct
2 Correct 32 ms 63040 KB Output is correct
3 Correct 35 ms 63068 KB Output is correct
4 Correct 34 ms 62972 KB Output is correct
5 Correct 34 ms 62944 KB Output is correct
6 Correct 32 ms 62984 KB Output is correct
7 Correct 32 ms 63060 KB Output is correct
8 Correct 35 ms 62956 KB Output is correct
9 Correct 35 ms 63052 KB Output is correct
10 Correct 33 ms 63040 KB Output is correct
11 Correct 32 ms 62992 KB Output is correct
12 Correct 38 ms 63052 KB Output is correct
13 Correct 34 ms 63044 KB Output is correct
14 Correct 38 ms 63040 KB Output is correct
15 Correct 35 ms 62972 KB Output is correct
16 Correct 40 ms 63032 KB Output is correct
17 Correct 35 ms 63404 KB Output is correct
18 Correct 38 ms 63572 KB Output is correct
19 Correct 39 ms 63564 KB Output is correct
20 Correct 45 ms 63724 KB Output is correct
21 Correct 37 ms 63568 KB Output is correct
22 Correct 40 ms 63564 KB Output is correct
23 Correct 38 ms 63524 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63012 KB Output is correct
2 Correct 32 ms 63040 KB Output is correct
3 Correct 35 ms 63068 KB Output is correct
4 Correct 34 ms 62972 KB Output is correct
5 Correct 34 ms 62944 KB Output is correct
6 Correct 32 ms 62984 KB Output is correct
7 Correct 32 ms 63060 KB Output is correct
8 Correct 35 ms 62956 KB Output is correct
9 Correct 35 ms 63052 KB Output is correct
10 Correct 33 ms 63040 KB Output is correct
11 Correct 32 ms 62992 KB Output is correct
12 Correct 38 ms 63052 KB Output is correct
13 Correct 34 ms 63044 KB Output is correct
14 Correct 38 ms 63040 KB Output is correct
15 Correct 35 ms 62972 KB Output is correct
16 Correct 40 ms 63032 KB Output is correct
17 Correct 35 ms 63404 KB Output is correct
18 Correct 38 ms 63572 KB Output is correct
19 Correct 39 ms 63564 KB Output is correct
20 Correct 45 ms 63724 KB Output is correct
21 Correct 37 ms 63568 KB Output is correct
22 Correct 40 ms 63564 KB Output is correct
23 Correct 38 ms 63524 KB Output is correct
24 Correct 384 ms 100244 KB Output is correct
25 Correct 581 ms 116772 KB Output is correct
26 Correct 423 ms 99996 KB Output is correct
27 Correct 555 ms 116036 KB Output is correct
28 Correct 483 ms 101988 KB Output is correct
29 Correct 356 ms 99980 KB Output is correct
30 Correct 875 ms 115932 KB Output is correct
31 Correct 209 ms 78924 KB Output is correct
32 Correct 279 ms 94288 KB Output is correct
33 Correct 649 ms 111248 KB Output is correct
34 Correct 744 ms 114164 KB Output is correct
35 Correct 825 ms 115792 KB Output is correct
36 Correct 820 ms 115468 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63012 KB Output is correct
2 Correct 32 ms 63040 KB Output is correct
3 Correct 35 ms 63068 KB Output is correct
4 Correct 34 ms 62972 KB Output is correct
5 Correct 34 ms 62944 KB Output is correct
6 Correct 32 ms 62984 KB Output is correct
7 Correct 32 ms 63060 KB Output is correct
8 Correct 35 ms 62956 KB Output is correct
9 Correct 35 ms 63052 KB Output is correct
10 Correct 33 ms 63040 KB Output is correct
11 Correct 32 ms 62992 KB Output is correct
12 Correct 38 ms 63052 KB Output is correct
13 Correct 34 ms 63044 KB Output is correct
14 Correct 38 ms 63040 KB Output is correct
15 Correct 35 ms 62972 KB Output is correct
16 Correct 40 ms 63032 KB Output is correct
17 Correct 35 ms 63404 KB Output is correct
18 Correct 38 ms 63572 KB Output is correct
19 Correct 39 ms 63564 KB Output is correct
20 Correct 45 ms 63724 KB Output is correct
21 Correct 37 ms 63568 KB Output is correct
22 Correct 40 ms 63564 KB Output is correct
23 Correct 38 ms 63524 KB Output is correct
24 Correct 384 ms 100244 KB Output is correct
25 Correct 581 ms 116772 KB Output is correct
26 Correct 423 ms 99996 KB Output is correct
27 Correct 555 ms 116036 KB Output is correct
28 Correct 483 ms 101988 KB Output is correct
29 Correct 356 ms 99980 KB Output is correct
30 Correct 875 ms 115932 KB Output is correct
31 Correct 209 ms 78924 KB Output is correct
32 Correct 279 ms 94288 KB Output is correct
33 Correct 649 ms 111248 KB Output is correct
34 Correct 744 ms 114164 KB Output is correct
35 Correct 825 ms 115792 KB Output is correct
36 Correct 820 ms 115468 KB Output is correct
37 Correct 399 ms 99784 KB Output is correct
38 Correct 576 ms 117316 KB Output is correct
39 Correct 388 ms 101272 KB Output is correct
40 Correct 387 ms 101508 KB Output is correct
41 Correct 32 ms 62996 KB Output is correct
42 Correct 926 ms 117080 KB Output is correct
43 Correct 633 ms 112652 KB Output is correct
44 Correct 775 ms 115444 KB Output is correct
45 Correct 821 ms 117160 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 63012 KB Output is correct
2 Correct 32 ms 63040 KB Output is correct
3 Correct 35 ms 63068 KB Output is correct
4 Correct 34 ms 62972 KB Output is correct
5 Correct 34 ms 62944 KB Output is correct
6 Correct 32 ms 62984 KB Output is correct
7 Correct 32 ms 63060 KB Output is correct
8 Correct 35 ms 62956 KB Output is correct
9 Correct 35 ms 63052 KB Output is correct
10 Correct 33 ms 63040 KB Output is correct
11 Correct 32 ms 62992 KB Output is correct
12 Correct 38 ms 63052 KB Output is correct
13 Correct 34 ms 63044 KB Output is correct
14 Correct 38 ms 63040 KB Output is correct
15 Correct 35 ms 62972 KB Output is correct
16 Correct 40 ms 63032 KB Output is correct
17 Correct 35 ms 63404 KB Output is correct
18 Correct 38 ms 63572 KB Output is correct
19 Correct 39 ms 63564 KB Output is correct
20 Correct 45 ms 63724 KB Output is correct
21 Correct 37 ms 63568 KB Output is correct
22 Correct 40 ms 63564 KB Output is correct
23 Correct 38 ms 63524 KB Output is correct
24 Correct 384 ms 100244 KB Output is correct
25 Correct 581 ms 116772 KB Output is correct
26 Correct 423 ms 99996 KB Output is correct
27 Correct 555 ms 116036 KB Output is correct
28 Correct 483 ms 101988 KB Output is correct
29 Correct 356 ms 99980 KB Output is correct
30 Correct 875 ms 115932 KB Output is correct
31 Correct 209 ms 78924 KB Output is correct
32 Correct 279 ms 94288 KB Output is correct
33 Correct 649 ms 111248 KB Output is correct
34 Correct 744 ms 114164 KB Output is correct
35 Correct 825 ms 115792 KB Output is correct
36 Correct 820 ms 115468 KB Output is correct
37 Correct 399 ms 99784 KB Output is correct
38 Correct 576 ms 117316 KB Output is correct
39 Correct 388 ms 101272 KB Output is correct
40 Correct 387 ms 101508 KB Output is correct
41 Correct 32 ms 62996 KB Output is correct
42 Correct 926 ms 117080 KB Output is correct
43 Correct 633 ms 112652 KB Output is correct
44 Correct 775 ms 115444 KB Output is correct
45 Correct 821 ms 117160 KB Output is correct
46 Correct 1917 ms 230680 KB Output is correct
47 Correct 2783 ms 301004 KB Output is correct
48 Correct 1762 ms 229216 KB Output is correct
49 Correct 1806 ms 228996 KB Output is correct
50 Correct 5130 ms 300592 KB Output is correct
51 Correct 3370 ms 273188 KB Output is correct
52 Correct 3990 ms 288172 KB Output is correct
53 Correct 4813 ms 299016 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 101372 KB Output is correct
2 Correct 443 ms 100632 KB Output is correct
3 Correct 367 ms 99772 KB Output is correct
4 Correct 414 ms 99308 KB Output is correct
5 Correct 39 ms 63040 KB Output is correct
6 Correct 424 ms 100788 KB Output is correct
7 Correct 125 ms 70348 KB Output is correct
8 Correct 264 ms 94496 KB Output is correct
9 Correct 376 ms 99800 KB Output is correct
10 Correct 371 ms 99884 KB Output is correct
11 Correct 314 ms 99724 KB Output is correct
12 Correct 31 ms 63012 KB Output is correct
13 Correct 32 ms 63040 KB Output is correct
14 Correct 35 ms 63068 KB Output is correct
15 Correct 34 ms 62972 KB Output is correct
16 Correct 34 ms 62944 KB Output is correct
17 Correct 32 ms 62984 KB Output is correct
18 Correct 32 ms 63060 KB Output is correct
19 Correct 35 ms 62956 KB Output is correct
20 Correct 35 ms 63052 KB Output is correct
21 Correct 33 ms 63040 KB Output is correct
22 Correct 32 ms 62992 KB Output is correct
23 Correct 38 ms 63052 KB Output is correct
24 Correct 34 ms 63044 KB Output is correct
25 Correct 38 ms 63040 KB Output is correct
26 Correct 35 ms 62972 KB Output is correct
27 Correct 40 ms 63032 KB Output is correct
28 Correct 35 ms 63404 KB Output is correct
29 Correct 38 ms 63572 KB Output is correct
30 Correct 39 ms 63564 KB Output is correct
31 Correct 45 ms 63724 KB Output is correct
32 Correct 37 ms 63568 KB Output is correct
33 Correct 40 ms 63564 KB Output is correct
34 Correct 38 ms 63524 KB Output is correct
35 Correct 384 ms 100244 KB Output is correct
36 Correct 581 ms 116772 KB Output is correct
37 Correct 423 ms 99996 KB Output is correct
38 Correct 555 ms 116036 KB Output is correct
39 Correct 483 ms 101988 KB Output is correct
40 Correct 356 ms 99980 KB Output is correct
41 Correct 875 ms 115932 KB Output is correct
42 Correct 209 ms 78924 KB Output is correct
43 Correct 279 ms 94288 KB Output is correct
44 Correct 649 ms 111248 KB Output is correct
45 Correct 744 ms 114164 KB Output is correct
46 Correct 825 ms 115792 KB Output is correct
47 Correct 820 ms 115468 KB Output is correct
48 Correct 399 ms 99784 KB Output is correct
49 Correct 576 ms 117316 KB Output is correct
50 Correct 388 ms 101272 KB Output is correct
51 Correct 387 ms 101508 KB Output is correct
52 Correct 32 ms 62996 KB Output is correct
53 Correct 926 ms 117080 KB Output is correct
54 Correct 633 ms 112652 KB Output is correct
55 Correct 775 ms 115444 KB Output is correct
56 Correct 821 ms 117160 KB Output is correct
57 Correct 415 ms 97940 KB Output is correct
58 Correct 556 ms 114020 KB Output is correct
59 Correct 373 ms 97980 KB Output is correct
60 Correct 364 ms 97988 KB Output is correct
61 Correct 823 ms 114132 KB Output is correct
62 Correct 33 ms 62924 KB Output is correct
63 Correct 875 ms 113740 KB Output is correct
64 Incorrect 629 ms 123360 KB Output isn't correct
65 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 101372 KB Output is correct
2 Correct 443 ms 100632 KB Output is correct
3 Correct 367 ms 99772 KB Output is correct
4 Correct 414 ms 99308 KB Output is correct
5 Correct 39 ms 63040 KB Output is correct
6 Correct 424 ms 100788 KB Output is correct
7 Correct 125 ms 70348 KB Output is correct
8 Correct 264 ms 94496 KB Output is correct
9 Correct 376 ms 99800 KB Output is correct
10 Correct 371 ms 99884 KB Output is correct
11 Correct 314 ms 99724 KB Output is correct
12 Correct 31 ms 63012 KB Output is correct
13 Correct 32 ms 63040 KB Output is correct
14 Correct 35 ms 63068 KB Output is correct
15 Correct 34 ms 62972 KB Output is correct
16 Correct 34 ms 62944 KB Output is correct
17 Correct 32 ms 62984 KB Output is correct
18 Correct 32 ms 63060 KB Output is correct
19 Correct 35 ms 62956 KB Output is correct
20 Correct 35 ms 63052 KB Output is correct
21 Correct 33 ms 63040 KB Output is correct
22 Correct 32 ms 62992 KB Output is correct
23 Correct 38 ms 63052 KB Output is correct
24 Correct 34 ms 63044 KB Output is correct
25 Correct 38 ms 63040 KB Output is correct
26 Correct 35 ms 62972 KB Output is correct
27 Correct 40 ms 63032 KB Output is correct
28 Correct 35 ms 63404 KB Output is correct
29 Correct 38 ms 63572 KB Output is correct
30 Correct 39 ms 63564 KB Output is correct
31 Correct 45 ms 63724 KB Output is correct
32 Correct 37 ms 63568 KB Output is correct
33 Correct 40 ms 63564 KB Output is correct
34 Correct 38 ms 63524 KB Output is correct
35 Correct 384 ms 100244 KB Output is correct
36 Correct 581 ms 116772 KB Output is correct
37 Correct 423 ms 99996 KB Output is correct
38 Correct 555 ms 116036 KB Output is correct
39 Correct 483 ms 101988 KB Output is correct
40 Correct 356 ms 99980 KB Output is correct
41 Correct 875 ms 115932 KB Output is correct
42 Correct 209 ms 78924 KB Output is correct
43 Correct 279 ms 94288 KB Output is correct
44 Correct 649 ms 111248 KB Output is correct
45 Correct 744 ms 114164 KB Output is correct
46 Correct 825 ms 115792 KB Output is correct
47 Correct 820 ms 115468 KB Output is correct
48 Correct 399 ms 99784 KB Output is correct
49 Correct 576 ms 117316 KB Output is correct
50 Correct 388 ms 101272 KB Output is correct
51 Correct 387 ms 101508 KB Output is correct
52 Correct 32 ms 62996 KB Output is correct
53 Correct 926 ms 117080 KB Output is correct
54 Correct 633 ms 112652 KB Output is correct
55 Correct 775 ms 115444 KB Output is correct
56 Correct 821 ms 117160 KB Output is correct
57 Correct 1917 ms 230680 KB Output is correct
58 Correct 2783 ms 301004 KB Output is correct
59 Correct 1762 ms 229216 KB Output is correct
60 Correct 1806 ms 228996 KB Output is correct
61 Correct 5130 ms 300592 KB Output is correct
62 Correct 3370 ms 273188 KB Output is correct
63 Correct 3990 ms 288172 KB Output is correct
64 Correct 4813 ms 299016 KB Output is correct
65 Correct 415 ms 97940 KB Output is correct
66 Correct 556 ms 114020 KB Output is correct
67 Correct 373 ms 97980 KB Output is correct
68 Correct 364 ms 97988 KB Output is correct
69 Correct 823 ms 114132 KB Output is correct
70 Correct 33 ms 62924 KB Output is correct
71 Correct 875 ms 113740 KB Output is correct
72 Incorrect 629 ms 123360 KB Output isn't correct
73 Halted 0 ms 0 KB -