oj.uz

Submission #708176

# Submission time Handle Problem Language Result Execution time Memory
708176 2023-03-11T08:52:27 Z LittleCube Two Dishes (JOI19_dishes) C++17
74 / 100
 3601 ms 193076 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll inf = 1'000'000'000'000'000'000;
const ll mxN = 1'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];
int rangeA[1000006], rangeB[1000006];

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;
    }
    rangeA[++N] = M;
    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';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 46684 KB Output is correct
2 Correct 393 ms 46444 KB Output is correct
3 Correct 405 ms 46344 KB Output is correct
4 Correct 409 ms 46452 KB Output is correct
5 Correct 5 ms 8220 KB Output is correct
6 Correct 466 ms 45848 KB Output is correct
7 Correct 92 ms 20436 KB Output is correct
8 Correct 304 ms 34468 KB Output is correct
9 Correct 407 ms 47392 KB Output is correct
10 Correct 365 ms 40388 KB Output is correct
11 Correct 360 ms 40816 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 3 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 3 ms 8148 KB Output is correct
9 Correct 3 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 4 ms 8136 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 3 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 3 ms 8148 KB Output is correct
9 Correct 3 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 4 ms 8136 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 6 ms 8528 KB Output is correct
18 Correct 6 ms 8532 KB Output is correct
19 Correct 7 ms 8464 KB Output is correct
20 Correct 6 ms 8532 KB Output is correct
21 Correct 7 ms 8532 KB Output is correct
22 Correct 6 ms 8404 KB Output is correct
23 Correct 9 ms 8532 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 3 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 3 ms 8148 KB Output is correct
9 Correct 3 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 4 ms 8136 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 6 ms 8528 KB Output is correct
18 Correct 6 ms 8532 KB Output is correct
19 Correct 7 ms 8464 KB Output is correct
20 Correct 6 ms 8532 KB Output is correct
21 Correct 7 ms 8532 KB Output is correct
22 Correct 6 ms 8404 KB Output is correct
23 Correct 9 ms 8532 KB Output is correct
24 Correct 385 ms 43600 KB Output is correct
25 Correct 397 ms 43596 KB Output is correct
26 Correct 405 ms 43596 KB Output is correct
27 Correct 436 ms 43628 KB Output is correct
28 Correct 454 ms 43816 KB Output is correct
29 Correct 404 ms 44464 KB Output is correct
30 Correct 562 ms 43812 KB Output is correct
31 Correct 103 ms 18948 KB Output is correct
32 Correct 254 ms 32752 KB Output is correct
33 Correct 455 ms 43208 KB Output is correct
34 Correct 541 ms 43392 KB Output is correct
35 Correct 552 ms 37364 KB Output is correct
36 Correct 534 ms 37332 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 3 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 3 ms 8148 KB Output is correct
9 Correct 3 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 4 ms 8136 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 6 ms 8528 KB Output is correct
18 Correct 6 ms 8532 KB Output is correct
19 Correct 7 ms 8464 KB Output is correct
20 Correct 6 ms 8532 KB Output is correct
21 Correct 7 ms 8532 KB Output is correct
22 Correct 6 ms 8404 KB Output is correct
23 Correct 9 ms 8532 KB Output is correct
24 Correct 385 ms 43600 KB Output is correct
25 Correct 397 ms 43596 KB Output is correct
26 Correct 405 ms 43596 KB Output is correct
27 Correct 436 ms 43628 KB Output is correct
28 Correct 454 ms 43816 KB Output is correct
29 Correct 404 ms 44464 KB Output is correct
30 Correct 562 ms 43812 KB Output is correct
31 Correct 103 ms 18948 KB Output is correct
32 Correct 254 ms 32752 KB Output is correct
33 Correct 455 ms 43208 KB Output is correct
34 Correct 541 ms 43392 KB Output is correct
35 Correct 552 ms 37364 KB Output is correct
36 Correct 534 ms 37332 KB Output is correct
37 Correct 421 ms 46740 KB Output is correct
38 Correct 401 ms 46824 KB Output is correct
39 Correct 402 ms 43980 KB Output is correct
40 Correct 401 ms 44052 KB Output is correct
41 Correct 3 ms 8148 KB Output is correct
42 Correct 639 ms 46872 KB Output is correct
43 Correct 529 ms 46016 KB Output is correct
44 Correct 608 ms 46340 KB Output is correct
45 Correct 549 ms 40352 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8148 KB Output is correct
2 Correct 3 ms 8148 KB Output is correct
3 Correct 4 ms 8148 KB Output is correct
4 Correct 4 ms 8148 KB Output is correct
5 Correct 3 ms 8148 KB Output is correct
6 Correct 3 ms 8148 KB Output is correct
7 Correct 4 ms 8148 KB Output is correct
8 Correct 3 ms 8148 KB Output is correct
9 Correct 3 ms 8148 KB Output is correct
10 Correct 3 ms 8148 KB Output is correct
11 Correct 4 ms 8148 KB Output is correct
12 Correct 4 ms 8148 KB Output is correct
13 Correct 4 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 4 ms 8136 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 6 ms 8528 KB Output is correct
18 Correct 6 ms 8532 KB Output is correct
19 Correct 7 ms 8464 KB Output is correct
20 Correct 6 ms 8532 KB Output is correct
21 Correct 7 ms 8532 KB Output is correct
22 Correct 6 ms 8404 KB Output is correct
23 Correct 9 ms 8532 KB Output is correct
24 Correct 385 ms 43600 KB Output is correct
25 Correct 397 ms 43596 KB Output is correct
26 Correct 405 ms 43596 KB Output is correct
27 Correct 436 ms 43628 KB Output is correct
28 Correct 454 ms 43816 KB Output is correct
29 Correct 404 ms 44464 KB Output is correct
30 Correct 562 ms 43812 KB Output is correct
31 Correct 103 ms 18948 KB Output is correct
32 Correct 254 ms 32752 KB Output is correct
33 Correct 455 ms 43208 KB Output is correct
34 Correct 541 ms 43392 KB Output is correct
35 Correct 552 ms 37364 KB Output is correct
36 Correct 534 ms 37332 KB Output is correct
37 Correct 421 ms 46740 KB Output is correct
38 Correct 401 ms 46824 KB Output is correct
39 Correct 402 ms 43980 KB Output is correct
40 Correct 401 ms 44052 KB Output is correct
41 Correct 3 ms 8148 KB Output is correct
42 Correct 639 ms 46872 KB Output is correct
43 Correct 529 ms 46016 KB Output is correct
44 Correct 608 ms 46340 KB Output is correct
45 Correct 549 ms 40352 KB Output is correct
46 Correct 2358 ms 193044 KB Output is correct
47 Correct 2179 ms 193076 KB Output is correct
48 Correct 2189 ms 179420 KB Output is correct
49 Correct 2136 ms 179364 KB Output is correct
50 Correct 3601 ms 192884 KB Output is correct
51 Correct 2943 ms 183996 KB Output is correct
52 Correct 3120 ms 182308 KB Output is correct
53 Correct 3353 ms 160348 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 46684 KB Output is correct
2 Correct 393 ms 46444 KB Output is correct
3 Correct 405 ms 46344 KB Output is correct
4 Correct 409 ms 46452 KB Output is correct
5 Correct 5 ms 8220 KB Output is correct
6 Correct 466 ms 45848 KB Output is correct
7 Correct 92 ms 20436 KB Output is correct
8 Correct 304 ms 34468 KB Output is correct
9 Correct 407 ms 47392 KB Output is correct
10 Correct 365 ms 40388 KB Output is correct
11 Correct 360 ms 40816 KB Output is correct
12 Correct 3 ms 8148 KB Output is correct
13 Correct 3 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 4 ms 8148 KB Output is correct
16 Correct 3 ms 8148 KB Output is correct
17 Correct 3 ms 8148 KB Output is correct
18 Correct 4 ms 8148 KB Output is correct
19 Correct 3 ms 8148 KB Output is correct
20 Correct 3 ms 8148 KB Output is correct
21 Correct 3 ms 8148 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct
23 Correct 4 ms 8148 KB Output is correct
24 Correct 4 ms 8148 KB Output is correct
25 Correct 4 ms 8148 KB Output is correct
26 Correct 4 ms 8136 KB Output is correct
27 Correct 4 ms 8148 KB Output is correct
28 Correct 6 ms 8528 KB Output is correct
29 Correct 6 ms 8532 KB Output is correct
30 Correct 7 ms 8464 KB Output is correct
31 Correct 6 ms 8532 KB Output is correct
32 Correct 7 ms 8532 KB Output is correct
33 Correct 6 ms 8404 KB Output is correct
34 Correct 9 ms 8532 KB Output is correct
35 Correct 385 ms 43600 KB Output is correct
36 Correct 397 ms 43596 KB Output is correct
37 Correct 405 ms 43596 KB Output is correct
38 Correct 436 ms 43628 KB Output is correct
39 Correct 454 ms 43816 KB Output is correct
40 Correct 404 ms 44464 KB Output is correct
41 Correct 562 ms 43812 KB Output is correct
42 Correct 103 ms 18948 KB Output is correct
43 Correct 254 ms 32752 KB Output is correct
44 Correct 455 ms 43208 KB Output is correct
45 Correct 541 ms 43392 KB Output is correct
46 Correct 552 ms 37364 KB Output is correct
47 Correct 534 ms 37332 KB Output is correct
48 Correct 421 ms 46740 KB Output is correct
49 Correct 401 ms 46824 KB Output is correct
50 Correct 402 ms 43980 KB Output is correct
51 Correct 401 ms 44052 KB Output is correct
52 Correct 3 ms 8148 KB Output is correct
53 Correct 639 ms 46872 KB Output is correct
54 Correct 529 ms 46016 KB Output is correct
55 Correct 608 ms 46340 KB Output is correct
56 Correct 549 ms 40352 KB Output is correct
57 Correct 403 ms 47188 KB Output is correct
58 Correct 440 ms 47164 KB Output is correct
59 Correct 395 ms 45124 KB Output is correct
60 Correct 441 ms 45000 KB Output is correct
61 Correct 596 ms 43676 KB Output is correct
62 Correct 4 ms 8148 KB Output is correct
63 Incorrect 592 ms 47008 KB Output isn't correct
64 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 46684 KB Output is correct
2 Correct 393 ms 46444 KB Output is correct
3 Correct 405 ms 46344 KB Output is correct
4 Correct 409 ms 46452 KB Output is correct
5 Correct 5 ms 8220 KB Output is correct
6 Correct 466 ms 45848 KB Output is correct
7 Correct 92 ms 20436 KB Output is correct
8 Correct 304 ms 34468 KB Output is correct
9 Correct 407 ms 47392 KB Output is correct
10 Correct 365 ms 40388 KB Output is correct
11 Correct 360 ms 40816 KB Output is correct
12 Correct 3 ms 8148 KB Output is correct
13 Correct 3 ms 8148 KB Output is correct
14 Correct 4 ms 8148 KB Output is correct
15 Correct 4 ms 8148 KB Output is correct
16 Correct 3 ms 8148 KB Output is correct
17 Correct 3 ms 8148 KB Output is correct
18 Correct 4 ms 8148 KB Output is correct
19 Correct 3 ms 8148 KB Output is correct
20 Correct 3 ms 8148 KB Output is correct
21 Correct 3 ms 8148 KB Output is correct
22 Correct 4 ms 8148 KB Output is correct
23 Correct 4 ms 8148 KB Output is correct
24 Correct 4 ms 8148 KB Output is correct
25 Correct 4 ms 8148 KB Output is correct
26 Correct 4 ms 8136 KB Output is correct
27 Correct 4 ms 8148 KB Output is correct
28 Correct 6 ms 8528 KB Output is correct
29 Correct 6 ms 8532 KB Output is correct
30 Correct 7 ms 8464 KB Output is correct
31 Correct 6 ms 8532 KB Output is correct
32 Correct 7 ms 8532 KB Output is correct
33 Correct 6 ms 8404 KB Output is correct
34 Correct 9 ms 8532 KB Output is correct
35 Correct 385 ms 43600 KB Output is correct
36 Correct 397 ms 43596 KB Output is correct
37 Correct 405 ms 43596 KB Output is correct
38 Correct 436 ms 43628 KB Output is correct
39 Correct 454 ms 43816 KB Output is correct
40 Correct 404 ms 44464 KB Output is correct
41 Correct 562 ms 43812 KB Output is correct
42 Correct 103 ms 18948 KB Output is correct
43 Correct 254 ms 32752 KB Output is correct
44 Correct 455 ms 43208 KB Output is correct
45 Correct 541 ms 43392 KB Output is correct
46 Correct 552 ms 37364 KB Output is correct
47 Correct 534 ms 37332 KB Output is correct
48 Correct 421 ms 46740 KB Output is correct
49 Correct 401 ms 46824 KB Output is correct
50 Correct 402 ms 43980 KB Output is correct
51 Correct 401 ms 44052 KB Output is correct
52 Correct 3 ms 8148 KB Output is correct
53 Correct 639 ms 46872 KB Output is correct
54 Correct 529 ms 46016 KB Output is correct
55 Correct 608 ms 46340 KB Output is correct
56 Correct 549 ms 40352 KB Output is correct
57 Correct 2358 ms 193044 KB Output is correct
58 Correct 2179 ms 193076 KB Output is correct
59 Correct 2189 ms 179420 KB Output is correct
60 Correct 2136 ms 179364 KB Output is correct
61 Correct 3601 ms 192884 KB Output is correct
62 Correct 2943 ms 183996 KB Output is correct
63 Correct 3120 ms 182308 KB Output is correct
64 Correct 3353 ms 160348 KB Output is correct
65 Correct 403 ms 47188 KB Output is correct
66 Correct 440 ms 47164 KB Output is correct
67 Correct 395 ms 45124 KB Output is correct
68 Correct 441 ms 45000 KB Output is correct
69 Correct 596 ms 43676 KB Output is correct
70 Correct 4 ms 8148 KB Output is correct
71 Incorrect 592 ms 47008 KB Output isn't correct
72 Halted 0 ms 0 KB -