oj.uz

Submission #708183

# Submission time Handle Problem Language Result Execution time Memory
708183 2023-03-11T09:07:35 Z LittleCube Two Dishes (JOI19_dishes) C++14
5 / 100
 544 ms 122828 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]] > i)
            ins[rangeB[i]].emplace_back(i);
    }
    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<>());
        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;
        }
    }
    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';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 109016 KB Output is correct
2 Correct 435 ms 117928 KB Output is correct
3 Correct 532 ms 121792 KB Output is correct
4 Correct 378 ms 105292 KB Output is correct
5 Correct 31 ms 62924 KB Output is correct
6 Correct 469 ms 117532 KB Output is correct
7 Correct 308 ms 91532 KB Output is correct
8 Correct 262 ms 93144 KB Output is correct
9 Correct 544 ms 122828 KB Output is correct
10 Correct 344 ms 99148 KB Output is correct
11 Correct 522 ms 116324 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62924 KB Output is correct
2 Correct 35 ms 62952 KB Output is correct
3 Correct 37 ms 63004 KB Output is correct
4 Correct 34 ms 62936 KB Output is correct
5 Correct 33 ms 63036 KB Output is correct
6 Correct 33 ms 62984 KB Output is correct
7 Correct 33 ms 63040 KB Output is correct
8 Correct 33 ms 63048 KB Output is correct
9 Correct 35 ms 63056 KB Output is correct
10 Incorrect 35 ms 63004 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62924 KB Output is correct
2 Correct 35 ms 62952 KB Output is correct
3 Correct 37 ms 63004 KB Output is correct
4 Correct 34 ms 62936 KB Output is correct
5 Correct 33 ms 63036 KB Output is correct
6 Correct 33 ms 62984 KB Output is correct
7 Correct 33 ms 63040 KB Output is correct
8 Correct 33 ms 63048 KB Output is correct
9 Correct 35 ms 63056 KB Output is correct
10 Incorrect 35 ms 63004 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62924 KB Output is correct
2 Correct 35 ms 62952 KB Output is correct
3 Correct 37 ms 63004 KB Output is correct
4 Correct 34 ms 62936 KB Output is correct
5 Correct 33 ms 63036 KB Output is correct
6 Correct 33 ms 62984 KB Output is correct
7 Correct 33 ms 63040 KB Output is correct
8 Correct 33 ms 63048 KB Output is correct
9 Correct 35 ms 63056 KB Output is correct
10 Incorrect 35 ms 63004 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62924 KB Output is correct
2 Correct 35 ms 62952 KB Output is correct
3 Correct 37 ms 63004 KB Output is correct
4 Correct 34 ms 62936 KB Output is correct
5 Correct 33 ms 63036 KB Output is correct
6 Correct 33 ms 62984 KB Output is correct
7 Correct 33 ms 63040 KB Output is correct
8 Correct 33 ms 63048 KB Output is correct
9 Correct 35 ms 63056 KB Output is correct
10 Incorrect 35 ms 63004 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62924 KB Output is correct
2 Correct 35 ms 62952 KB Output is correct
3 Correct 37 ms 63004 KB Output is correct
4 Correct 34 ms 62936 KB Output is correct
5 Correct 33 ms 63036 KB Output is correct
6 Correct 33 ms 62984 KB Output is correct
7 Correct 33 ms 63040 KB Output is correct
8 Correct 33 ms 63048 KB Output is correct
9 Correct 35 ms 63056 KB Output is correct
10 Incorrect 35 ms 63004 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 109016 KB Output is correct
2 Correct 435 ms 117928 KB Output is correct
3 Correct 532 ms 121792 KB Output is correct
4 Correct 378 ms 105292 KB Output is correct
5 Correct 31 ms 62924 KB Output is correct
6 Correct 469 ms 117532 KB Output is correct
7 Correct 308 ms 91532 KB Output is correct
8 Correct 262 ms 93144 KB Output is correct
9 Correct 544 ms 122828 KB Output is correct
10 Correct 344 ms 99148 KB Output is correct
11 Correct 522 ms 116324 KB Output is correct
12 Correct 40 ms 62924 KB Output is correct
13 Correct 35 ms 62952 KB Output is correct
14 Correct 37 ms 63004 KB Output is correct
15 Correct 34 ms 62936 KB Output is correct
16 Correct 33 ms 63036 KB Output is correct
17 Correct 33 ms 62984 KB Output is correct
18 Correct 33 ms 63040 KB Output is correct
19 Correct 33 ms 63048 KB Output is correct
20 Correct 35 ms 63056 KB Output is correct
21 Incorrect 35 ms 63004 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 109016 KB Output is correct
2 Correct 435 ms 117928 KB Output is correct
3 Correct 532 ms 121792 KB Output is correct
4 Correct 378 ms 105292 KB Output is correct
5 Correct 31 ms 62924 KB Output is correct
6 Correct 469 ms 117532 KB Output is correct
7 Correct 308 ms 91532 KB Output is correct
8 Correct 262 ms 93144 KB Output is correct
9 Correct 544 ms 122828 KB Output is correct
10 Correct 344 ms 99148 KB Output is correct
11 Correct 522 ms 116324 KB Output is correct
12 Correct 40 ms 62924 KB Output is correct
13 Correct 35 ms 62952 KB Output is correct
14 Correct 37 ms 63004 KB Output is correct
15 Correct 34 ms 62936 KB Output is correct
16 Correct 33 ms 63036 KB Output is correct
17 Correct 33 ms 62984 KB Output is correct
18 Correct 33 ms 63040 KB Output is correct
19 Correct 33 ms 63048 KB Output is correct
20 Correct 35 ms 63056 KB Output is correct
21 Incorrect 35 ms 63004 KB Output isn't correct
22 Halted 0 ms 0 KB -