oj.uz

Submission #708226

# Submission time Handle Problem Language Result Execution time Memory
708226 2023-03-11T10:51:02 Z LittleCube Two Dishes (JOI19_dishes) C++14
74 / 100
 5304 ms 333500 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 - 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]);
        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] && 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 << ' ' << 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';
}

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 131644 KB Output is correct
2 Correct 444 ms 130888 KB Output is correct
3 Correct 412 ms 129988 KB Output is correct
4 Correct 447 ms 129424 KB Output is correct
5 Correct 55 ms 94348 KB Output is correct
6 Correct 448 ms 130916 KB Output is correct
7 Correct 136 ms 100552 KB Output is correct
8 Correct 292 ms 124488 KB Output is correct
9 Correct 400 ms 130032 KB Output is correct
10 Correct 378 ms 129968 KB Output is correct
11 Correct 356 ms 129952 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94284 KB Output is correct
2 Correct 47 ms 94304 KB Output is correct
3 Correct 57 ms 94396 KB Output is correct
4 Correct 52 ms 94324 KB Output is correct
5 Correct 47 ms 94352 KB Output is correct
6 Correct 50 ms 94316 KB Output is correct
7 Correct 52 ms 94348 KB Output is correct
8 Correct 47 ms 94256 KB Output is correct
9 Correct 58 ms 94356 KB Output is correct
10 Correct 55 ms 94264 KB Output is correct
11 Correct 62 ms 94300 KB Output is correct
12 Correct 51 ms 94284 KB Output is correct
13 Correct 49 ms 94284 KB Output is correct
14 Correct 51 ms 94316 KB Output is correct
15 Correct 57 ms 94284 KB Output is correct
16 Correct 54 ms 94308 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94284 KB Output is correct
2 Correct 47 ms 94304 KB Output is correct
3 Correct 57 ms 94396 KB Output is correct
4 Correct 52 ms 94324 KB Output is correct
5 Correct 47 ms 94352 KB Output is correct
6 Correct 50 ms 94316 KB Output is correct
7 Correct 52 ms 94348 KB Output is correct
8 Correct 47 ms 94256 KB Output is correct
9 Correct 58 ms 94356 KB Output is correct
10 Correct 55 ms 94264 KB Output is correct
11 Correct 62 ms 94300 KB Output is correct
12 Correct 51 ms 94284 KB Output is correct
13 Correct 49 ms 94284 KB Output is correct
14 Correct 51 ms 94316 KB Output is correct
15 Correct 57 ms 94284 KB Output is correct
16 Correct 54 ms 94308 KB Output is correct
17 Correct 48 ms 94796 KB Output is correct
18 Correct 53 ms 94868 KB Output is correct
19 Correct 52 ms 94956 KB Output is correct
20 Correct 49 ms 94796 KB Output is correct
21 Correct 55 ms 94796 KB Output is correct
22 Correct 51 ms 94840 KB Output is correct
23 Correct 55 ms 94960 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94284 KB Output is correct
2 Correct 47 ms 94304 KB Output is correct
3 Correct 57 ms 94396 KB Output is correct
4 Correct 52 ms 94324 KB Output is correct
5 Correct 47 ms 94352 KB Output is correct
6 Correct 50 ms 94316 KB Output is correct
7 Correct 52 ms 94348 KB Output is correct
8 Correct 47 ms 94256 KB Output is correct
9 Correct 58 ms 94356 KB Output is correct
10 Correct 55 ms 94264 KB Output is correct
11 Correct 62 ms 94300 KB Output is correct
12 Correct 51 ms 94284 KB Output is correct
13 Correct 49 ms 94284 KB Output is correct
14 Correct 51 ms 94316 KB Output is correct
15 Correct 57 ms 94284 KB Output is correct
16 Correct 54 ms 94308 KB Output is correct
17 Correct 48 ms 94796 KB Output is correct
18 Correct 53 ms 94868 KB Output is correct
19 Correct 52 ms 94956 KB Output is correct
20 Correct 49 ms 94796 KB Output is correct
21 Correct 55 ms 94796 KB Output is correct
22 Correct 51 ms 94840 KB Output is correct
23 Correct 55 ms 94960 KB Output is correct
24 Correct 412 ms 130252 KB Output is correct
25 Correct 619 ms 146948 KB Output is correct
26 Correct 361 ms 130256 KB Output is correct
27 Correct 616 ms 146232 KB Output is correct
28 Correct 549 ms 132100 KB Output is correct
29 Correct 366 ms 130204 KB Output is correct
30 Correct 904 ms 145936 KB Output is correct
31 Correct 234 ms 109048 KB Output is correct
32 Correct 270 ms 124668 KB Output is correct
33 Correct 642 ms 141508 KB Output is correct
34 Correct 858 ms 144368 KB Output is correct
35 Correct 829 ms 145856 KB Output is correct
36 Correct 833 ms 145644 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94284 KB Output is correct
2 Correct 47 ms 94304 KB Output is correct
3 Correct 57 ms 94396 KB Output is correct
4 Correct 52 ms 94324 KB Output is correct
5 Correct 47 ms 94352 KB Output is correct
6 Correct 50 ms 94316 KB Output is correct
7 Correct 52 ms 94348 KB Output is correct
8 Correct 47 ms 94256 KB Output is correct
9 Correct 58 ms 94356 KB Output is correct
10 Correct 55 ms 94264 KB Output is correct
11 Correct 62 ms 94300 KB Output is correct
12 Correct 51 ms 94284 KB Output is correct
13 Correct 49 ms 94284 KB Output is correct
14 Correct 51 ms 94316 KB Output is correct
15 Correct 57 ms 94284 KB Output is correct
16 Correct 54 ms 94308 KB Output is correct
17 Correct 48 ms 94796 KB Output is correct
18 Correct 53 ms 94868 KB Output is correct
19 Correct 52 ms 94956 KB Output is correct
20 Correct 49 ms 94796 KB Output is correct
21 Correct 55 ms 94796 KB Output is correct
22 Correct 51 ms 94840 KB Output is correct
23 Correct 55 ms 94960 KB Output is correct
24 Correct 412 ms 130252 KB Output is correct
25 Correct 619 ms 146948 KB Output is correct
26 Correct 361 ms 130256 KB Output is correct
27 Correct 616 ms 146232 KB Output is correct
28 Correct 549 ms 132100 KB Output is correct
29 Correct 366 ms 130204 KB Output is correct
30 Correct 904 ms 145936 KB Output is correct
31 Correct 234 ms 109048 KB Output is correct
32 Correct 270 ms 124668 KB Output is correct
33 Correct 642 ms 141508 KB Output is correct
34 Correct 858 ms 144368 KB Output is correct
35 Correct 829 ms 145856 KB Output is correct
36 Correct 833 ms 145644 KB Output is correct
37 Correct 424 ms 130016 KB Output is correct
38 Correct 653 ms 146792 KB Output is correct
39 Correct 452 ms 130900 KB Output is correct
40 Correct 415 ms 130732 KB Output is correct
41 Correct 73 ms 94272 KB Output is correct
42 Correct 973 ms 146472 KB Output is correct
43 Correct 652 ms 142016 KB Output is correct
44 Correct 801 ms 144924 KB Output is correct
45 Correct 857 ms 146748 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94284 KB Output is correct
2 Correct 47 ms 94304 KB Output is correct
3 Correct 57 ms 94396 KB Output is correct
4 Correct 52 ms 94324 KB Output is correct
5 Correct 47 ms 94352 KB Output is correct
6 Correct 50 ms 94316 KB Output is correct
7 Correct 52 ms 94348 KB Output is correct
8 Correct 47 ms 94256 KB Output is correct
9 Correct 58 ms 94356 KB Output is correct
10 Correct 55 ms 94264 KB Output is correct
11 Correct 62 ms 94300 KB Output is correct
12 Correct 51 ms 94284 KB Output is correct
13 Correct 49 ms 94284 KB Output is correct
14 Correct 51 ms 94316 KB Output is correct
15 Correct 57 ms 94284 KB Output is correct
16 Correct 54 ms 94308 KB Output is correct
17 Correct 48 ms 94796 KB Output is correct
18 Correct 53 ms 94868 KB Output is correct
19 Correct 52 ms 94956 KB Output is correct
20 Correct 49 ms 94796 KB Output is correct
21 Correct 55 ms 94796 KB Output is correct
22 Correct 51 ms 94840 KB Output is correct
23 Correct 55 ms 94960 KB Output is correct
24 Correct 412 ms 130252 KB Output is correct
25 Correct 619 ms 146948 KB Output is correct
26 Correct 361 ms 130256 KB Output is correct
27 Correct 616 ms 146232 KB Output is correct
28 Correct 549 ms 132100 KB Output is correct
29 Correct 366 ms 130204 KB Output is correct
30 Correct 904 ms 145936 KB Output is correct
31 Correct 234 ms 109048 KB Output is correct
32 Correct 270 ms 124668 KB Output is correct
33 Correct 642 ms 141508 KB Output is correct
34 Correct 858 ms 144368 KB Output is correct
35 Correct 829 ms 145856 KB Output is correct
36 Correct 833 ms 145644 KB Output is correct
37 Correct 424 ms 130016 KB Output is correct
38 Correct 653 ms 146792 KB Output is correct
39 Correct 452 ms 130900 KB Output is correct
40 Correct 415 ms 130732 KB Output is correct
41 Correct 73 ms 94272 KB Output is correct
42 Correct 973 ms 146472 KB Output is correct
43 Correct 652 ms 142016 KB Output is correct
44 Correct 801 ms 144924 KB Output is correct
45 Correct 857 ms 146748 KB Output is correct
46 Correct 2132 ms 261196 KB Output is correct
47 Correct 3061 ms 333500 KB Output is correct
48 Correct 1879 ms 261100 KB Output is correct
49 Correct 1844 ms 260864 KB Output is correct
50 Correct 5304 ms 333044 KB Output is correct
51 Correct 3422 ms 306008 KB Output is correct
52 Correct 4173 ms 320752 KB Output is correct
53 Correct 4977 ms 332672 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 131644 KB Output is correct
2 Correct 444 ms 130888 KB Output is correct
3 Correct 412 ms 129988 KB Output is correct
4 Correct 447 ms 129424 KB Output is correct
5 Correct 55 ms 94348 KB Output is correct
6 Correct 448 ms 130916 KB Output is correct
7 Correct 136 ms 100552 KB Output is correct
8 Correct 292 ms 124488 KB Output is correct
9 Correct 400 ms 130032 KB Output is correct
10 Correct 378 ms 129968 KB Output is correct
11 Correct 356 ms 129952 KB Output is correct
12 Correct 47 ms 94284 KB Output is correct
13 Correct 47 ms 94304 KB Output is correct
14 Correct 57 ms 94396 KB Output is correct
15 Correct 52 ms 94324 KB Output is correct
16 Correct 47 ms 94352 KB Output is correct
17 Correct 50 ms 94316 KB Output is correct
18 Correct 52 ms 94348 KB Output is correct
19 Correct 47 ms 94256 KB Output is correct
20 Correct 58 ms 94356 KB Output is correct
21 Correct 55 ms 94264 KB Output is correct
22 Correct 62 ms 94300 KB Output is correct
23 Correct 51 ms 94284 KB Output is correct
24 Correct 49 ms 94284 KB Output is correct
25 Correct 51 ms 94316 KB Output is correct
26 Correct 57 ms 94284 KB Output is correct
27 Correct 54 ms 94308 KB Output is correct
28 Correct 48 ms 94796 KB Output is correct
29 Correct 53 ms 94868 KB Output is correct
30 Correct 52 ms 94956 KB Output is correct
31 Correct 49 ms 94796 KB Output is correct
32 Correct 55 ms 94796 KB Output is correct
33 Correct 51 ms 94840 KB Output is correct
34 Correct 55 ms 94960 KB Output is correct
35 Correct 412 ms 130252 KB Output is correct
36 Correct 619 ms 146948 KB Output is correct
37 Correct 361 ms 130256 KB Output is correct
38 Correct 616 ms 146232 KB Output is correct
39 Correct 549 ms 132100 KB Output is correct
40 Correct 366 ms 130204 KB Output is correct
41 Correct 904 ms 145936 KB Output is correct
42 Correct 234 ms 109048 KB Output is correct
43 Correct 270 ms 124668 KB Output is correct
44 Correct 642 ms 141508 KB Output is correct
45 Correct 858 ms 144368 KB Output is correct
46 Correct 829 ms 145856 KB Output is correct
47 Correct 833 ms 145644 KB Output is correct
48 Correct 424 ms 130016 KB Output is correct
49 Correct 653 ms 146792 KB Output is correct
50 Correct 452 ms 130900 KB Output is correct
51 Correct 415 ms 130732 KB Output is correct
52 Correct 73 ms 94272 KB Output is correct
53 Correct 973 ms 146472 KB Output is correct
54 Correct 652 ms 142016 KB Output is correct
55 Correct 801 ms 144924 KB Output is correct
56 Correct 857 ms 146748 KB Output is correct
57 Correct 405 ms 131588 KB Output is correct
58 Correct 583 ms 146452 KB Output is correct
59 Correct 409 ms 130396 KB Output is correct
60 Correct 407 ms 130420 KB Output is correct
61 Correct 908 ms 146684 KB Output is correct
62 Correct 52 ms 94296 KB Output is correct
63 Incorrect 902 ms 146188 KB Output isn't correct
64 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 131644 KB Output is correct
2 Correct 444 ms 130888 KB Output is correct
3 Correct 412 ms 129988 KB Output is correct
4 Correct 447 ms 129424 KB Output is correct
5 Correct 55 ms 94348 KB Output is correct
6 Correct 448 ms 130916 KB Output is correct
7 Correct 136 ms 100552 KB Output is correct
8 Correct 292 ms 124488 KB Output is correct
9 Correct 400 ms 130032 KB Output is correct
10 Correct 378 ms 129968 KB Output is correct
11 Correct 356 ms 129952 KB Output is correct
12 Correct 47 ms 94284 KB Output is correct
13 Correct 47 ms 94304 KB Output is correct
14 Correct 57 ms 94396 KB Output is correct
15 Correct 52 ms 94324 KB Output is correct
16 Correct 47 ms 94352 KB Output is correct
17 Correct 50 ms 94316 KB Output is correct
18 Correct 52 ms 94348 KB Output is correct
19 Correct 47 ms 94256 KB Output is correct
20 Correct 58 ms 94356 KB Output is correct
21 Correct 55 ms 94264 KB Output is correct
22 Correct 62 ms 94300 KB Output is correct
23 Correct 51 ms 94284 KB Output is correct
24 Correct 49 ms 94284 KB Output is correct
25 Correct 51 ms 94316 KB Output is correct
26 Correct 57 ms 94284 KB Output is correct
27 Correct 54 ms 94308 KB Output is correct
28 Correct 48 ms 94796 KB Output is correct
29 Correct 53 ms 94868 KB Output is correct
30 Correct 52 ms 94956 KB Output is correct
31 Correct 49 ms 94796 KB Output is correct
32 Correct 55 ms 94796 KB Output is correct
33 Correct 51 ms 94840 KB Output is correct
34 Correct 55 ms 94960 KB Output is correct
35 Correct 412 ms 130252 KB Output is correct
36 Correct 619 ms 146948 KB Output is correct
37 Correct 361 ms 130256 KB Output is correct
38 Correct 616 ms 146232 KB Output is correct
39 Correct 549 ms 132100 KB Output is correct
40 Correct 366 ms 130204 KB Output is correct
41 Correct 904 ms 145936 KB Output is correct
42 Correct 234 ms 109048 KB Output is correct
43 Correct 270 ms 124668 KB Output is correct
44 Correct 642 ms 141508 KB Output is correct
45 Correct 858 ms 144368 KB Output is correct
46 Correct 829 ms 145856 KB Output is correct
47 Correct 833 ms 145644 KB Output is correct
48 Correct 424 ms 130016 KB Output is correct
49 Correct 653 ms 146792 KB Output is correct
50 Correct 452 ms 130900 KB Output is correct
51 Correct 415 ms 130732 KB Output is correct
52 Correct 73 ms 94272 KB Output is correct
53 Correct 973 ms 146472 KB Output is correct
54 Correct 652 ms 142016 KB Output is correct
55 Correct 801 ms 144924 KB Output is correct
56 Correct 857 ms 146748 KB Output is correct
57 Correct 2132 ms 261196 KB Output is correct
58 Correct 3061 ms 333500 KB Output is correct
59 Correct 1879 ms 261100 KB Output is correct
60 Correct 1844 ms 260864 KB Output is correct
61 Correct 5304 ms 333044 KB Output is correct
62 Correct 3422 ms 306008 KB Output is correct
63 Correct 4173 ms 320752 KB Output is correct
64 Correct 4977 ms 332672 KB Output is correct
65 Correct 405 ms 131588 KB Output is correct
66 Correct 583 ms 146452 KB Output is correct
67 Correct 409 ms 130396 KB Output is correct
68 Correct 407 ms 130420 KB Output is correct
69 Correct 908 ms 146684 KB Output is correct
70 Correct 52 ms 94296 KB Output is correct
71 Incorrect 902 ms 146188 KB Output isn't correct
72 Halted 0 ms 0 KB -