oj.uz

Submission #944604

# Submission time Handle Problem Language Result Execution time Memory
944604 2024-03-13T01:38:30 Z LOLOLO Two Dishes (JOI19_dishes) C++17
74 / 100
 5288 ms 291968 KB 
#include <bits/stdc++.h>
typedef long long ll;
 
#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
 
using namespace std;
const int N = 1e6 + 10;
ll A[N], B[N], SA[N], SB[N], S[N], T[N], Q[N], P[N];
vector <pair <ll, ll>> pos[N];
ll lim = -1e16;

struct ST{
    vector <ll> seg, laz, ass;
    ST(int n) {
        for (int i = 0; i <= n * 4 + 100; i++) {
            seg.pb(0);
            laz.pb(0);
            ass.pb(lim);
        }
    }

    void push(int id, int l, int r) {
        seg[id] = max(seg[id] + laz[id], ass[id]);
        if (l == r) {
            laz[id] = 0;
            ass[id] = lim;
            return;
        }

        ll t = laz[id];
        ass[id * 2] = max(ass[id * 2] + t, ass[id]);
        ass[id * 2 + 1] = max(ass[id * 2 + 1] + t, ass[id]);
        laz[id * 2] += t;
        laz[id * 2 + 1] += t;
        laz[id] = 0;
        ass[id] = lim;
    }

    void upd(int id, int l, int r, int u, int v, ll t) {
        push(id, l, r);
        if (l > v || r < u)
            return;

        if (l >= u && r <= v) {
            laz[id] += t;
            ass[id] += t;
            push(id, l, r);
            return;
        }

        int m = (l + r) / 2;
        upd(id * 2, l, m, u, v, t);
        upd(id * 2 + 1, m + 1, r, u, v, t);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
   } 

    void range(int id, int l, int r, int u, int v, ll val) {
        push(id, l, r);
        if (l > v || r < u)
            return;

        if (l >= u && r <= v) {
            ass[id] = val;
            push(id, l, r);
            return;
        }

        int m = (l + r) / 2;
        range(id * 2, l, m, u, v, val);
        range(id * 2 + 1, m + 1, r, u, v, val);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }

    ll get(int id, int l, int r, int u, int v) {
        push(id, l, r);
        if (u > v || l > v || r < u)
            return -1e12;

        if (l >= u && r <= v)
            return seg[id];

        int m = (l + r) / 2;
        return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
    }
};

vector <pair <ll, ll>> compress(vector < pair <ll, ll>> &v) {
    vector <pair <ll, ll>> st;
    for (auto x : v) {
        if (st.empty() || st.back().f != x.f) {
            st.pb(x);
        } else {
            st[sz(st) - 1].s += x.s;
        }
    }
    return st;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll ans = 0;
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> A[i] >> S[i] >> P[i];
        SA[i] = SA[i - 1] + A[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> B[i] >> T[i] >> Q[i];
        SB[i] = SB[i - 1] + B[i];
    }

    for (int i = 1; i <= n; i++) {
        if (SA[i] > S[i])
            continue;
        
        ans += P[i];
        int id = upper_bound(SB, SB + 1 + m, S[i] - SA[i]) - SB - 1;
        pos[i - 1].pb({id + 1, -P[i]});
    }
 
    for (int i = 1; i <= m; i++) {
        if (SB[i] > T[i])
            continue;
 
        int id = upper_bound(SA, SA + 1 + n, T[i] - SB[i]) - SA - 1;
        pos[id].pb({i, Q[i]});
    }

    for (int i = 1; i <= n; i++) {
        sort(all(pos[i]));
        pos[i] = compress(pos[i]);
    }

    ST seg(m);

    for (int i = 0; i <= n; i++) {
        for (auto x : pos[i]) {
            seg.upd(1, 0, m, x.f, m, x.s);
        }

        reverse(all(pos[i]));
        int lx = m;
        for (auto x : pos[i]) {
            seg.range(1, 0, m, x.f, lx, seg.get(1, 0, m, 0, x.f));
            lx = x.f -1;
        }
    }

    cout << seg.get(1, 0, m, m, m) + ans << '\n';
    return 0; 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 88508 KB Output is correct
2 Correct 452 ms 88952 KB Output is correct
3 Correct 339 ms 93912 KB Output is correct
4 Correct 299 ms 84112 KB Output is correct
5 Correct 8 ms 35676 KB Output is correct
6 Correct 408 ms 86804 KB Output is correct
7 Correct 239 ms 77060 KB Output is correct
8 Correct 80 ms 53176 KB Output is correct
9 Correct 419 ms 94744 KB Output is correct
10 Correct 334 ms 85804 KB Output is correct
11 Correct 308 ms 91100 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35416 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 8 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35440 KB Output is correct
6 Correct 8 ms 35572 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 8 ms 35420 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 8 ms 35420 KB Output is correct
11 Correct 7 ms 35420 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 7 ms 35496 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 7 ms 35540 KB Output is correct
16 Correct 7 ms 35420 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35416 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 8 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35440 KB Output is correct
6 Correct 8 ms 35572 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 8 ms 35420 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 8 ms 35420 KB Output is correct
11 Correct 7 ms 35420 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 7 ms 35496 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 7 ms 35540 KB Output is correct
16 Correct 7 ms 35420 KB Output is correct
17 Correct 12 ms 37944 KB Output is correct
18 Correct 11 ms 37980 KB Output is correct
19 Correct 12 ms 37976 KB Output is correct
20 Correct 10 ms 35932 KB Output is correct
21 Correct 11 ms 37956 KB Output is correct
22 Correct 14 ms 37980 KB Output is correct
23 Correct 12 ms 37820 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35416 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 8 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35440 KB Output is correct
6 Correct 8 ms 35572 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 8 ms 35420 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 8 ms 35420 KB Output is correct
11 Correct 7 ms 35420 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 7 ms 35496 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 7 ms 35540 KB Output is correct
16 Correct 7 ms 35420 KB Output is correct
17 Correct 12 ms 37944 KB Output is correct
18 Correct 11 ms 37980 KB Output is correct
19 Correct 12 ms 37976 KB Output is correct
20 Correct 10 ms 35932 KB Output is correct
21 Correct 11 ms 37956 KB Output is correct
22 Correct 14 ms 37980 KB Output is correct
23 Correct 12 ms 37820 KB Output is correct
24 Correct 567 ms 87788 KB Output is correct
25 Correct 341 ms 86968 KB Output is correct
26 Correct 426 ms 83040 KB Output is correct
27 Correct 330 ms 82192 KB Output is correct
28 Correct 461 ms 84664 KB Output is correct
29 Correct 330 ms 92236 KB Output is correct
30 Correct 784 ms 90000 KB Output is correct
31 Correct 243 ms 68300 KB Output is correct
32 Correct 77 ms 51964 KB Output is correct
33 Correct 446 ms 82760 KB Output is correct
34 Correct 609 ms 86204 KB Output is correct
35 Correct 754 ms 83072 KB Output is correct
36 Correct 743 ms 85640 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35416 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 8 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35440 KB Output is correct
6 Correct 8 ms 35572 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 8 ms 35420 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 8 ms 35420 KB Output is correct
11 Correct 7 ms 35420 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 7 ms 35496 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 7 ms 35540 KB Output is correct
16 Correct 7 ms 35420 KB Output is correct
17 Correct 12 ms 37944 KB Output is correct
18 Correct 11 ms 37980 KB Output is correct
19 Correct 12 ms 37976 KB Output is correct
20 Correct 10 ms 35932 KB Output is correct
21 Correct 11 ms 37956 KB Output is correct
22 Correct 14 ms 37980 KB Output is correct
23 Correct 12 ms 37820 KB Output is correct
24 Correct 567 ms 87788 KB Output is correct
25 Correct 341 ms 86968 KB Output is correct
26 Correct 426 ms 83040 KB Output is correct
27 Correct 330 ms 82192 KB Output is correct
28 Correct 461 ms 84664 KB Output is correct
29 Correct 330 ms 92236 KB Output is correct
30 Correct 784 ms 90000 KB Output is correct
31 Correct 243 ms 68300 KB Output is correct
32 Correct 77 ms 51964 KB Output is correct
33 Correct 446 ms 82760 KB Output is correct
34 Correct 609 ms 86204 KB Output is correct
35 Correct 754 ms 83072 KB Output is correct
36 Correct 743 ms 85640 KB Output is correct
37 Correct 504 ms 85324 KB Output is correct
38 Correct 446 ms 84640 KB Output is correct
39 Correct 385 ms 85292 KB Output is correct
40 Correct 412 ms 87688 KB Output is correct
41 Correct 11 ms 35416 KB Output is correct
42 Correct 829 ms 89268 KB Output is correct
43 Correct 432 ms 82160 KB Output is correct
44 Correct 630 ms 86636 KB Output is correct
45 Correct 749 ms 81680 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35416 KB Output is correct
2 Correct 7 ms 35420 KB Output is correct
3 Correct 8 ms 35420 KB Output is correct
4 Correct 7 ms 35420 KB Output is correct
5 Correct 7 ms 35440 KB Output is correct
6 Correct 8 ms 35572 KB Output is correct
7 Correct 7 ms 35676 KB Output is correct
8 Correct 8 ms 35420 KB Output is correct
9 Correct 7 ms 35420 KB Output is correct
10 Correct 8 ms 35420 KB Output is correct
11 Correct 7 ms 35420 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 7 ms 35496 KB Output is correct
14 Correct 7 ms 35420 KB Output is correct
15 Correct 7 ms 35540 KB Output is correct
16 Correct 7 ms 35420 KB Output is correct
17 Correct 12 ms 37944 KB Output is correct
18 Correct 11 ms 37980 KB Output is correct
19 Correct 12 ms 37976 KB Output is correct
20 Correct 10 ms 35932 KB Output is correct
21 Correct 11 ms 37956 KB Output is correct
22 Correct 14 ms 37980 KB Output is correct
23 Correct 12 ms 37820 KB Output is correct
24 Correct 567 ms 87788 KB Output is correct
25 Correct 341 ms 86968 KB Output is correct
26 Correct 426 ms 83040 KB Output is correct
27 Correct 330 ms 82192 KB Output is correct
28 Correct 461 ms 84664 KB Output is correct
29 Correct 330 ms 92236 KB Output is correct
30 Correct 784 ms 90000 KB Output is correct
31 Correct 243 ms 68300 KB Output is correct
32 Correct 77 ms 51964 KB Output is correct
33 Correct 446 ms 82760 KB Output is correct
34 Correct 609 ms 86204 KB Output is correct
35 Correct 754 ms 83072 KB Output is correct
36 Correct 743 ms 85640 KB Output is correct
37 Correct 504 ms 85324 KB Output is correct
38 Correct 446 ms 84640 KB Output is correct
39 Correct 385 ms 85292 KB Output is correct
40 Correct 412 ms 87688 KB Output is correct
41 Correct 11 ms 35416 KB Output is correct
42 Correct 829 ms 89268 KB Output is correct
43 Correct 432 ms 82160 KB Output is correct
44 Correct 630 ms 86636 KB Output is correct
45 Correct 749 ms 81680 KB Output is correct
46 Correct 2377 ms 267336 KB Output is correct
47 Correct 1847 ms 272948 KB Output is correct
48 Correct 1810 ms 270032 KB Output is correct
49 Correct 1842 ms 270000 KB Output is correct
50 Correct 5288 ms 291968 KB Output is correct
51 Correct 2711 ms 258240 KB Output is correct
52 Correct 3828 ms 273272 KB Output is correct
53 Correct 5017 ms 272288 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 88508 KB Output is correct
2 Correct 452 ms 88952 KB Output is correct
3 Correct 339 ms 93912 KB Output is correct
4 Correct 299 ms 84112 KB Output is correct
5 Correct 8 ms 35676 KB Output is correct
6 Correct 408 ms 86804 KB Output is correct
7 Correct 239 ms 77060 KB Output is correct
8 Correct 80 ms 53176 KB Output is correct
9 Correct 419 ms 94744 KB Output is correct
10 Correct 334 ms 85804 KB Output is correct
11 Correct 308 ms 91100 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 7 ms 35420 KB Output is correct
14 Correct 8 ms 35420 KB Output is correct
15 Correct 7 ms 35420 KB Output is correct
16 Correct 7 ms 35440 KB Output is correct
17 Correct 8 ms 35572 KB Output is correct
18 Correct 7 ms 35676 KB Output is correct
19 Correct 8 ms 35420 KB Output is correct
20 Correct 7 ms 35420 KB Output is correct
21 Correct 8 ms 35420 KB Output is correct
22 Correct 7 ms 35420 KB Output is correct
23 Correct 7 ms 35420 KB Output is correct
24 Correct 7 ms 35496 KB Output is correct
25 Correct 7 ms 35420 KB Output is correct
26 Correct 7 ms 35540 KB Output is correct
27 Correct 7 ms 35420 KB Output is correct
28 Correct 12 ms 37944 KB Output is correct
29 Correct 11 ms 37980 KB Output is correct
30 Correct 12 ms 37976 KB Output is correct
31 Correct 10 ms 35932 KB Output is correct
32 Correct 11 ms 37956 KB Output is correct
33 Correct 14 ms 37980 KB Output is correct
34 Correct 12 ms 37820 KB Output is correct
35 Correct 567 ms 87788 KB Output is correct
36 Correct 341 ms 86968 KB Output is correct
37 Correct 426 ms 83040 KB Output is correct
38 Correct 330 ms 82192 KB Output is correct
39 Correct 461 ms 84664 KB Output is correct
40 Correct 330 ms 92236 KB Output is correct
41 Correct 784 ms 90000 KB Output is correct
42 Correct 243 ms 68300 KB Output is correct
43 Correct 77 ms 51964 KB Output is correct
44 Correct 446 ms 82760 KB Output is correct
45 Correct 609 ms 86204 KB Output is correct
46 Correct 754 ms 83072 KB Output is correct
47 Correct 743 ms 85640 KB Output is correct
48 Correct 504 ms 85324 KB Output is correct
49 Correct 446 ms 84640 KB Output is correct
50 Correct 385 ms 85292 KB Output is correct
51 Correct 412 ms 87688 KB Output is correct
52 Correct 11 ms 35416 KB Output is correct
53 Correct 829 ms 89268 KB Output is correct
54 Correct 432 ms 82160 KB Output is correct
55 Correct 630 ms 86636 KB Output is correct
56 Correct 749 ms 81680 KB Output is correct
57 Incorrect 439 ms 86044 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 88508 KB Output is correct
2 Correct 452 ms 88952 KB Output is correct
3 Correct 339 ms 93912 KB Output is correct
4 Correct 299 ms 84112 KB Output is correct
5 Correct 8 ms 35676 KB Output is correct
6 Correct 408 ms 86804 KB Output is correct
7 Correct 239 ms 77060 KB Output is correct
8 Correct 80 ms 53176 KB Output is correct
9 Correct 419 ms 94744 KB Output is correct
10 Correct 334 ms 85804 KB Output is correct
11 Correct 308 ms 91100 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 7 ms 35420 KB Output is correct
14 Correct 8 ms 35420 KB Output is correct
15 Correct 7 ms 35420 KB Output is correct
16 Correct 7 ms 35440 KB Output is correct
17 Correct 8 ms 35572 KB Output is correct
18 Correct 7 ms 35676 KB Output is correct
19 Correct 8 ms 35420 KB Output is correct
20 Correct 7 ms 35420 KB Output is correct
21 Correct 8 ms 35420 KB Output is correct
22 Correct 7 ms 35420 KB Output is correct
23 Correct 7 ms 35420 KB Output is correct
24 Correct 7 ms 35496 KB Output is correct
25 Correct 7 ms 35420 KB Output is correct
26 Correct 7 ms 35540 KB Output is correct
27 Correct 7 ms 35420 KB Output is correct
28 Correct 12 ms 37944 KB Output is correct
29 Correct 11 ms 37980 KB Output is correct
30 Correct 12 ms 37976 KB Output is correct
31 Correct 10 ms 35932 KB Output is correct
32 Correct 11 ms 37956 KB Output is correct
33 Correct 14 ms 37980 KB Output is correct
34 Correct 12 ms 37820 KB Output is correct
35 Correct 567 ms 87788 KB Output is correct
36 Correct 341 ms 86968 KB Output is correct
37 Correct 426 ms 83040 KB Output is correct
38 Correct 330 ms 82192 KB Output is correct
39 Correct 461 ms 84664 KB Output is correct
40 Correct 330 ms 92236 KB Output is correct
41 Correct 784 ms 90000 KB Output is correct
42 Correct 243 ms 68300 KB Output is correct
43 Correct 77 ms 51964 KB Output is correct
44 Correct 446 ms 82760 KB Output is correct
45 Correct 609 ms 86204 KB Output is correct
46 Correct 754 ms 83072 KB Output is correct
47 Correct 743 ms 85640 KB Output is correct
48 Correct 504 ms 85324 KB Output is correct
49 Correct 446 ms 84640 KB Output is correct
50 Correct 385 ms 85292 KB Output is correct
51 Correct 412 ms 87688 KB Output is correct
52 Correct 11 ms 35416 KB Output is correct
53 Correct 829 ms 89268 KB Output is correct
54 Correct 432 ms 82160 KB Output is correct
55 Correct 630 ms 86636 KB Output is correct
56 Correct 749 ms 81680 KB Output is correct
57 Correct 2377 ms 267336 KB Output is correct
58 Correct 1847 ms 272948 KB Output is correct
59 Correct 1810 ms 270032 KB Output is correct
60 Correct 1842 ms 270000 KB Output is correct
61 Correct 5288 ms 291968 KB Output is correct
62 Correct 2711 ms 258240 KB Output is correct
63 Correct 3828 ms 273272 KB Output is correct
64 Correct 5017 ms 272288 KB Output is correct
65 Incorrect 439 ms 86044 KB Output isn't correct
66 Halted 0 ms 0 KB -