oj.uz

Submission #709462

# Submission time Handle Problem Language Result Execution time Memory
709462 2023-03-13T16:05:49 Z PixelCat Two Dishes (JOI19_dishes) C++14
74 / 100
 6596 ms 252344 KB 
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 1000010;
const int INF = 8e18;

// range add, range max
#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    struct Node {
        int mx, add;
    } a[MAXN << 2];
    void init(int val) {
        For(i, 0, (MAXN << 2) - 1) {
            a[i].mx = val;
            a[i].add = 0;
        }
    }
    void _add(int id, int x) {
        a[id].add += x;
        a[id].mx += x;
    }
    void pull(int id) {
        a[id].mx = max(a[L(id)].mx, a[R(id)].mx);
    }
    void push(int id) {
        if(a[id].add != 0) {
            _add(L(id), a[id].add);
            _add(R(id), a[id].add);
            a[id].add = 0;
        }
    }
    void add(int id, int l, int r, int L, int R, int x) {
        // if(l > R || r < L) return;
        if(l >= L && r <= R) {
            _add(id, x);
            return;
        }
        push(id);
        int m = (l + r) / 2;
        if(L <= m) add(L(id), l, m, L, R, x);
        if(R > m)  add(R(id), m + 1, r, L, R, x);
        pull(id);
    }
    void set(int id, int l, int r, int i, int x) {
        if(l == r) {
            // a[id].mx = max(a[id].mx, x);
            a[id].mx = x;
            a[id].add = 0;
            return;
        }
        push(id);
        int m = (l + r) / 2;
        if(i <= m) set(L(id), l, m, i, x);
        else       set(R(id), m + 1, r, i, x);
        pull(id);
    }
    int ask(int id, int l, int r, int L, int R) {
        if(l >= L && r <= R) return a[id].mx;
        push(id);
        int m = (l + r) / 2;
        int res = -INF;
        if(L <= m) res = max(res, ask(L(id), l, m, L, R));
        if(R > m)  res = max(res, ask(R(id), m + 1, r, L, R));
        pull(id);
        return res;
    }
} seg, seg2, seg3;

int a1[MAXN];
int s1[MAXN];
int p1[MAXN];
int pr1[MAXN];
int t1[MAXN];

int a2[MAXN];
int s2[MAXN];
int p2[MAXN];
int pr2[MAXN];
int t2[MAXN];

// int su[MAXN][MAXN];
int dp[MAXN];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // NYA =^-w-^=
    int n, m;
// #define QWQ
#ifndef QWQ
    cin >> n >> m;
    assert(n <= MAXN);
    For(i, 1, n) {
        cin >> a1[i] >> s1[i] >> p1[i];
        pr1[i] = pr1[i - 1] + a1[i];
    }
    For(i, 1, m) {
        cin >> a2[i] >> s2[i] >> p2[i];
        pr2[i] = pr2[i - 1] + a2[i];
    }
#else
    mt19937 rng(48763);
    n = m = 5;
    For(i, 1, n) {
        a1[i] = rng() % 10 + 1;
        s1[i] = rng() % 100 + 1;
        // p1[i] = rng() % 21 - 10;
        p1[i] = 1;
        pr1[i] = pr1[i - 1] + a1[i];
    }
    For(i, 1, m) {
        a2[i] = rng() % 10 + 1;
        s2[i] = rng() % 100 + 1;
        // p2[i] = rng() % 21 - 10;
        p2[i] = 1;
        pr2[i] = pr2[i - 1] + a2[i];
    }
#endif

    vector<pair<pii, int>> v;
    For(i, 1, n) {
        auto it = upper_bound(pr2, pr2 + m + 1, s1[i] - pr1[i]);
        t1[i] = it - pr2 - 1;
        if(t1[i] >= 0) v.eb(pii(t1[i], i), 1);
    }
    
    For(i, 1, m) {
        auto it = upper_bound(pr1, pr1 + n + 1, s2[i] - pr2[i]);
        t2[i] = it - pr1 - 1;
        if(t2[i] < n && t2[i] >= 0 && t1[t2[i] + 1] != i - 1) v.eb(pii(i - 1, t2[i] + 1), 0);
    }

    // For(i, 1, n) cout << t1[i] << " \n"[i == n];
    // For(i, 1, m) cout << t2[i] << " \n"[i == m];

    sort(all(v));
    reverse(all(v));
    
    seg.init(-INF);
    seg2.init(0);
    for(auto &i:v) if(i.S) {
        seg2.add(0, 0, n, i.F.S, n, p1[i.F.S]);
    }
    seg.set(0, 0, n, 0, 0);

    For(it, 0, m) {
        if(it && (t2[it] >= 0)) {
            seg.add(0, 0, n, 0, t2[it], p2[it]);
        }
        while(sz(v) && v.back().F.F == it) {
            int i = v.back().F.S;
            int owo = v.back().S;
            // cout << v.back().F.F << " " << i << " " << owo << "\n" << flush;
            v.pop_back();

            int val = seg.ask(0, 0, n, 0, i - 1) + seg2.ask(0, 0, n, i, i);
            if(owo) {
                seg2.add(0, 0, n, i, n, -p1[i]);
                seg.add(0, 0, n, i, n, p1[i]);
            }
            
            val = max(val, seg.ask(0, 0, n, i, i) + seg2.ask(0, 0, n, i, i));
            seg.set(0, 0, n, i, val - seg2.ask(0, 0, n, i, i));

            // cout << i << " " << it << " " << val << "\n";
        }
    }
    cout << seg.ask(0, 0, n, 0, n) << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 148512 KB Output is correct
2 Correct 511 ms 148588 KB Output is correct
3 Correct 458 ms 147644 KB Output is correct
4 Correct 380 ms 145624 KB Output is correct
5 Correct 50 ms 125596 KB Output is correct
6 Correct 523 ms 147928 KB Output is correct
7 Correct 132 ms 135176 KB Output is correct
8 Correct 393 ms 139948 KB Output is correct
9 Correct 486 ms 147620 KB Output is correct
10 Correct 448 ms 147740 KB Output is correct
11 Correct 402 ms 147964 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125516 KB Output is correct
2 Correct 49 ms 125516 KB Output is correct
3 Correct 53 ms 125516 KB Output is correct
4 Correct 53 ms 125516 KB Output is correct
5 Correct 50 ms 125516 KB Output is correct
6 Correct 48 ms 125584 KB Output is correct
7 Correct 47 ms 125576 KB Output is correct
8 Correct 52 ms 125568 KB Output is correct
9 Correct 52 ms 125600 KB Output is correct
10 Correct 49 ms 125564 KB Output is correct
11 Correct 61 ms 125576 KB Output is correct
12 Correct 65 ms 125608 KB Output is correct
13 Correct 58 ms 125612 KB Output is correct
14 Correct 70 ms 125548 KB Output is correct
15 Correct 69 ms 125516 KB Output is correct
16 Correct 57 ms 125588 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125516 KB Output is correct
2 Correct 49 ms 125516 KB Output is correct
3 Correct 53 ms 125516 KB Output is correct
4 Correct 53 ms 125516 KB Output is correct
5 Correct 50 ms 125516 KB Output is correct
6 Correct 48 ms 125584 KB Output is correct
7 Correct 47 ms 125576 KB Output is correct
8 Correct 52 ms 125568 KB Output is correct
9 Correct 52 ms 125600 KB Output is correct
10 Correct 49 ms 125564 KB Output is correct
11 Correct 61 ms 125576 KB Output is correct
12 Correct 65 ms 125608 KB Output is correct
13 Correct 58 ms 125612 KB Output is correct
14 Correct 70 ms 125548 KB Output is correct
15 Correct 69 ms 125516 KB Output is correct
16 Correct 57 ms 125588 KB Output is correct
17 Correct 57 ms 125904 KB Output is correct
18 Correct 61 ms 126032 KB Output is correct
19 Correct 68 ms 126040 KB Output is correct
20 Correct 57 ms 125900 KB Output is correct
21 Correct 55 ms 125968 KB Output is correct
22 Correct 60 ms 125964 KB Output is correct
23 Correct 55 ms 126032 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125516 KB Output is correct
2 Correct 49 ms 125516 KB Output is correct
3 Correct 53 ms 125516 KB Output is correct
4 Correct 53 ms 125516 KB Output is correct
5 Correct 50 ms 125516 KB Output is correct
6 Correct 48 ms 125584 KB Output is correct
7 Correct 47 ms 125576 KB Output is correct
8 Correct 52 ms 125568 KB Output is correct
9 Correct 52 ms 125600 KB Output is correct
10 Correct 49 ms 125564 KB Output is correct
11 Correct 61 ms 125576 KB Output is correct
12 Correct 65 ms 125608 KB Output is correct
13 Correct 58 ms 125612 KB Output is correct
14 Correct 70 ms 125548 KB Output is correct
15 Correct 69 ms 125516 KB Output is correct
16 Correct 57 ms 125588 KB Output is correct
17 Correct 57 ms 125904 KB Output is correct
18 Correct 61 ms 126032 KB Output is correct
19 Correct 68 ms 126040 KB Output is correct
20 Correct 57 ms 125900 KB Output is correct
21 Correct 55 ms 125968 KB Output is correct
22 Correct 60 ms 125964 KB Output is correct
23 Correct 55 ms 126032 KB Output is correct
24 Correct 488 ms 147756 KB Output is correct
25 Correct 501 ms 150152 KB Output is correct
26 Correct 418 ms 147768 KB Output is correct
27 Correct 515 ms 150344 KB Output is correct
28 Correct 602 ms 148432 KB Output is correct
29 Correct 420 ms 147780 KB Output is correct
30 Correct 903 ms 152204 KB Output is correct
31 Correct 123 ms 137620 KB Output is correct
32 Correct 380 ms 140004 KB Output is correct
33 Correct 548 ms 147460 KB Output is correct
34 Correct 840 ms 151212 KB Output is correct
35 Correct 930 ms 152420 KB Output is correct
36 Correct 902 ms 152188 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125516 KB Output is correct
2 Correct 49 ms 125516 KB Output is correct
3 Correct 53 ms 125516 KB Output is correct
4 Correct 53 ms 125516 KB Output is correct
5 Correct 50 ms 125516 KB Output is correct
6 Correct 48 ms 125584 KB Output is correct
7 Correct 47 ms 125576 KB Output is correct
8 Correct 52 ms 125568 KB Output is correct
9 Correct 52 ms 125600 KB Output is correct
10 Correct 49 ms 125564 KB Output is correct
11 Correct 61 ms 125576 KB Output is correct
12 Correct 65 ms 125608 KB Output is correct
13 Correct 58 ms 125612 KB Output is correct
14 Correct 70 ms 125548 KB Output is correct
15 Correct 69 ms 125516 KB Output is correct
16 Correct 57 ms 125588 KB Output is correct
17 Correct 57 ms 125904 KB Output is correct
18 Correct 61 ms 126032 KB Output is correct
19 Correct 68 ms 126040 KB Output is correct
20 Correct 57 ms 125900 KB Output is correct
21 Correct 55 ms 125968 KB Output is correct
22 Correct 60 ms 125964 KB Output is correct
23 Correct 55 ms 126032 KB Output is correct
24 Correct 488 ms 147756 KB Output is correct
25 Correct 501 ms 150152 KB Output is correct
26 Correct 418 ms 147768 KB Output is correct
27 Correct 515 ms 150344 KB Output is correct
28 Correct 602 ms 148432 KB Output is correct
29 Correct 420 ms 147780 KB Output is correct
30 Correct 903 ms 152204 KB Output is correct
31 Correct 123 ms 137620 KB Output is correct
32 Correct 380 ms 140004 KB Output is correct
33 Correct 548 ms 147460 KB Output is correct
34 Correct 840 ms 151212 KB Output is correct
35 Correct 930 ms 152420 KB Output is correct
36 Correct 902 ms 152188 KB Output is correct
37 Correct 530 ms 147724 KB Output is correct
38 Correct 579 ms 150088 KB Output is correct
39 Correct 458 ms 147884 KB Output is correct
40 Correct 460 ms 148108 KB Output is correct
41 Correct 53 ms 125536 KB Output is correct
42 Correct 1010 ms 152216 KB Output is correct
43 Correct 614 ms 147344 KB Output is correct
44 Correct 938 ms 151048 KB Output is correct
45 Correct 1000 ms 152604 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125516 KB Output is correct
2 Correct 49 ms 125516 KB Output is correct
3 Correct 53 ms 125516 KB Output is correct
4 Correct 53 ms 125516 KB Output is correct
5 Correct 50 ms 125516 KB Output is correct
6 Correct 48 ms 125584 KB Output is correct
7 Correct 47 ms 125576 KB Output is correct
8 Correct 52 ms 125568 KB Output is correct
9 Correct 52 ms 125600 KB Output is correct
10 Correct 49 ms 125564 KB Output is correct
11 Correct 61 ms 125576 KB Output is correct
12 Correct 65 ms 125608 KB Output is correct
13 Correct 58 ms 125612 KB Output is correct
14 Correct 70 ms 125548 KB Output is correct
15 Correct 69 ms 125516 KB Output is correct
16 Correct 57 ms 125588 KB Output is correct
17 Correct 57 ms 125904 KB Output is correct
18 Correct 61 ms 126032 KB Output is correct
19 Correct 68 ms 126040 KB Output is correct
20 Correct 57 ms 125900 KB Output is correct
21 Correct 55 ms 125968 KB Output is correct
22 Correct 60 ms 125964 KB Output is correct
23 Correct 55 ms 126032 KB Output is correct
24 Correct 488 ms 147756 KB Output is correct
25 Correct 501 ms 150152 KB Output is correct
26 Correct 418 ms 147768 KB Output is correct
27 Correct 515 ms 150344 KB Output is correct
28 Correct 602 ms 148432 KB Output is correct
29 Correct 420 ms 147780 KB Output is correct
30 Correct 903 ms 152204 KB Output is correct
31 Correct 123 ms 137620 KB Output is correct
32 Correct 380 ms 140004 KB Output is correct
33 Correct 548 ms 147460 KB Output is correct
34 Correct 840 ms 151212 KB Output is correct
35 Correct 930 ms 152420 KB Output is correct
36 Correct 902 ms 152188 KB Output is correct
37 Correct 530 ms 147724 KB Output is correct
38 Correct 579 ms 150088 KB Output is correct
39 Correct 458 ms 147884 KB Output is correct
40 Correct 460 ms 148108 KB Output is correct
41 Correct 53 ms 125536 KB Output is correct
42 Correct 1010 ms 152216 KB Output is correct
43 Correct 614 ms 147344 KB Output is correct
44 Correct 938 ms 151048 KB Output is correct
45 Correct 1000 ms 152604 KB Output is correct
46 Correct 2277 ms 228388 KB Output is correct
47 Correct 2735 ms 241364 KB Output is correct
48 Correct 2319 ms 229644 KB Output is correct
49 Correct 2535 ms 229408 KB Output is correct
50 Correct 6596 ms 252344 KB Output is correct
51 Correct 3433 ms 225448 KB Output is correct
52 Correct 4780 ms 241960 KB Output is correct
53 Correct 5766 ms 249404 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 148512 KB Output is correct
2 Correct 511 ms 148588 KB Output is correct
3 Correct 458 ms 147644 KB Output is correct
4 Correct 380 ms 145624 KB Output is correct
5 Correct 50 ms 125596 KB Output is correct
6 Correct 523 ms 147928 KB Output is correct
7 Correct 132 ms 135176 KB Output is correct
8 Correct 393 ms 139948 KB Output is correct
9 Correct 486 ms 147620 KB Output is correct
10 Correct 448 ms 147740 KB Output is correct
11 Correct 402 ms 147964 KB Output is correct
12 Correct 48 ms 125516 KB Output is correct
13 Correct 49 ms 125516 KB Output is correct
14 Correct 53 ms 125516 KB Output is correct
15 Correct 53 ms 125516 KB Output is correct
16 Correct 50 ms 125516 KB Output is correct
17 Correct 48 ms 125584 KB Output is correct
18 Correct 47 ms 125576 KB Output is correct
19 Correct 52 ms 125568 KB Output is correct
20 Correct 52 ms 125600 KB Output is correct
21 Correct 49 ms 125564 KB Output is correct
22 Correct 61 ms 125576 KB Output is correct
23 Correct 65 ms 125608 KB Output is correct
24 Correct 58 ms 125612 KB Output is correct
25 Correct 70 ms 125548 KB Output is correct
26 Correct 69 ms 125516 KB Output is correct
27 Correct 57 ms 125588 KB Output is correct
28 Correct 57 ms 125904 KB Output is correct
29 Correct 61 ms 126032 KB Output is correct
30 Correct 68 ms 126040 KB Output is correct
31 Correct 57 ms 125900 KB Output is correct
32 Correct 55 ms 125968 KB Output is correct
33 Correct 60 ms 125964 KB Output is correct
34 Correct 55 ms 126032 KB Output is correct
35 Correct 488 ms 147756 KB Output is correct
36 Correct 501 ms 150152 KB Output is correct
37 Correct 418 ms 147768 KB Output is correct
38 Correct 515 ms 150344 KB Output is correct
39 Correct 602 ms 148432 KB Output is correct
40 Correct 420 ms 147780 KB Output is correct
41 Correct 903 ms 152204 KB Output is correct
42 Correct 123 ms 137620 KB Output is correct
43 Correct 380 ms 140004 KB Output is correct
44 Correct 548 ms 147460 KB Output is correct
45 Correct 840 ms 151212 KB Output is correct
46 Correct 930 ms 152420 KB Output is correct
47 Correct 902 ms 152188 KB Output is correct
48 Correct 530 ms 147724 KB Output is correct
49 Correct 579 ms 150088 KB Output is correct
50 Correct 458 ms 147884 KB Output is correct
51 Correct 460 ms 148108 KB Output is correct
52 Correct 53 ms 125536 KB Output is correct
53 Correct 1010 ms 152216 KB Output is correct
54 Correct 614 ms 147344 KB Output is correct
55 Correct 938 ms 151048 KB Output is correct
56 Correct 1000 ms 152604 KB Output is correct
57 Correct 527 ms 147528 KB Output is correct
58 Correct 578 ms 150120 KB Output is correct
59 Correct 481 ms 148992 KB Output is correct
60 Correct 546 ms 148924 KB Output is correct
61 Correct 952 ms 153676 KB Output is correct
62 Correct 59 ms 125520 KB Output is correct
63 Incorrect 974 ms 153428 KB Output isn't correct
64 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 148512 KB Output is correct
2 Correct 511 ms 148588 KB Output is correct
3 Correct 458 ms 147644 KB Output is correct
4 Correct 380 ms 145624 KB Output is correct
5 Correct 50 ms 125596 KB Output is correct
6 Correct 523 ms 147928 KB Output is correct
7 Correct 132 ms 135176 KB Output is correct
8 Correct 393 ms 139948 KB Output is correct
9 Correct 486 ms 147620 KB Output is correct
10 Correct 448 ms 147740 KB Output is correct
11 Correct 402 ms 147964 KB Output is correct
12 Correct 48 ms 125516 KB Output is correct
13 Correct 49 ms 125516 KB Output is correct
14 Correct 53 ms 125516 KB Output is correct
15 Correct 53 ms 125516 KB Output is correct
16 Correct 50 ms 125516 KB Output is correct
17 Correct 48 ms 125584 KB Output is correct
18 Correct 47 ms 125576 KB Output is correct
19 Correct 52 ms 125568 KB Output is correct
20 Correct 52 ms 125600 KB Output is correct
21 Correct 49 ms 125564 KB Output is correct
22 Correct 61 ms 125576 KB Output is correct
23 Correct 65 ms 125608 KB Output is correct
24 Correct 58 ms 125612 KB Output is correct
25 Correct 70 ms 125548 KB Output is correct
26 Correct 69 ms 125516 KB Output is correct
27 Correct 57 ms 125588 KB Output is correct
28 Correct 57 ms 125904 KB Output is correct
29 Correct 61 ms 126032 KB Output is correct
30 Correct 68 ms 126040 KB Output is correct
31 Correct 57 ms 125900 KB Output is correct
32 Correct 55 ms 125968 KB Output is correct
33 Correct 60 ms 125964 KB Output is correct
34 Correct 55 ms 126032 KB Output is correct
35 Correct 488 ms 147756 KB Output is correct
36 Correct 501 ms 150152 KB Output is correct
37 Correct 418 ms 147768 KB Output is correct
38 Correct 515 ms 150344 KB Output is correct
39 Correct 602 ms 148432 KB Output is correct
40 Correct 420 ms 147780 KB Output is correct
41 Correct 903 ms 152204 KB Output is correct
42 Correct 123 ms 137620 KB Output is correct
43 Correct 380 ms 140004 KB Output is correct
44 Correct 548 ms 147460 KB Output is correct
45 Correct 840 ms 151212 KB Output is correct
46 Correct 930 ms 152420 KB Output is correct
47 Correct 902 ms 152188 KB Output is correct
48 Correct 530 ms 147724 KB Output is correct
49 Correct 579 ms 150088 KB Output is correct
50 Correct 458 ms 147884 KB Output is correct
51 Correct 460 ms 148108 KB Output is correct
52 Correct 53 ms 125536 KB Output is correct
53 Correct 1010 ms 152216 KB Output is correct
54 Correct 614 ms 147344 KB Output is correct
55 Correct 938 ms 151048 KB Output is correct
56 Correct 1000 ms 152604 KB Output is correct
57 Correct 2277 ms 228388 KB Output is correct
58 Correct 2735 ms 241364 KB Output is correct
59 Correct 2319 ms 229644 KB Output is correct
60 Correct 2535 ms 229408 KB Output is correct
61 Correct 6596 ms 252344 KB Output is correct
62 Correct 3433 ms 225448 KB Output is correct
63 Correct 4780 ms 241960 KB Output is correct
64 Correct 5766 ms 249404 KB Output is correct
65 Correct 527 ms 147528 KB Output is correct
66 Correct 578 ms 150120 KB Output is correct
67 Correct 481 ms 148992 KB Output is correct
68 Correct 546 ms 148924 KB Output is correct
69 Correct 952 ms 153676 KB Output is correct
70 Correct 59 ms 125520 KB Output is correct
71 Incorrect 974 ms 153428 KB Output isn't correct
72 Halted 0 ms 0 KB -