oj.uz

Submission #709698

# Submission time Handle Problem Language Result Execution time Memory
709698 2023-03-14T08:05:32 Z PixelCat Two Dishes (JOI19_dishes) C++14
100 / 100
 5433 ms 319520 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) {
        if(a[id].mx == -INF) return;
        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;

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 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);
    }

    v.eb(pii(m, n + 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 + 1, i.F.S, n + 1, p1[i.F.S]);
    }
    seg.set(0, 0, n + 1, 0, 0);

    For(it, 0, m) {
        if(it && (t2[it] >= 0)) {
            seg.add(0, 0, n + 1, 0, t2[it], p2[it]);
        }
        int last = 0;
        while(sz(v) && v.back().F.F == it) {
            int i = v.back().F.S;
            int owo = v.back().S;
            v.pop_back();

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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 147928 KB Output is correct
2 Correct 449 ms 147884 KB Output is correct
3 Correct 423 ms 146948 KB Output is correct
4 Correct 344 ms 145164 KB Output is correct
5 Correct 49 ms 125532 KB Output is correct
6 Correct 461 ms 147164 KB Output is correct
7 Correct 127 ms 134224 KB Output is correct
8 Correct 318 ms 139116 KB Output is correct
9 Correct 440 ms 147028 KB Output is correct
10 Correct 406 ms 146968 KB Output is correct
11 Correct 386 ms 147004 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125556 KB Output is correct
2 Correct 50 ms 125596 KB Output is correct
3 Correct 53 ms 125532 KB Output is correct
4 Correct 53 ms 125520 KB Output is correct
5 Correct 52 ms 125516 KB Output is correct
6 Correct 49 ms 125512 KB Output is correct
7 Correct 49 ms 125596 KB Output is correct
8 Correct 48 ms 125516 KB Output is correct
9 Correct 51 ms 125516 KB Output is correct
10 Correct 50 ms 125556 KB Output is correct
11 Correct 51 ms 125644 KB Output is correct
12 Correct 49 ms 125564 KB Output is correct
13 Correct 48 ms 125520 KB Output is correct
14 Correct 53 ms 125632 KB Output is correct
15 Correct 49 ms 125520 KB Output is correct
16 Correct 48 ms 125596 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125556 KB Output is correct
2 Correct 50 ms 125596 KB Output is correct
3 Correct 53 ms 125532 KB Output is correct
4 Correct 53 ms 125520 KB Output is correct
5 Correct 52 ms 125516 KB Output is correct
6 Correct 49 ms 125512 KB Output is correct
7 Correct 49 ms 125596 KB Output is correct
8 Correct 48 ms 125516 KB Output is correct
9 Correct 51 ms 125516 KB Output is correct
10 Correct 50 ms 125556 KB Output is correct
11 Correct 51 ms 125644 KB Output is correct
12 Correct 49 ms 125564 KB Output is correct
13 Correct 48 ms 125520 KB Output is correct
14 Correct 53 ms 125632 KB Output is correct
15 Correct 49 ms 125520 KB Output is correct
16 Correct 48 ms 125596 KB Output is correct
17 Correct 54 ms 126064 KB Output is correct
18 Correct 54 ms 125964 KB Output is correct
19 Correct 55 ms 126040 KB Output is correct
20 Correct 53 ms 125896 KB Output is correct
21 Correct 55 ms 125992 KB Output is correct
22 Correct 54 ms 125964 KB Output is correct
23 Correct 60 ms 125960 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125556 KB Output is correct
2 Correct 50 ms 125596 KB Output is correct
3 Correct 53 ms 125532 KB Output is correct
4 Correct 53 ms 125520 KB Output is correct
5 Correct 52 ms 125516 KB Output is correct
6 Correct 49 ms 125512 KB Output is correct
7 Correct 49 ms 125596 KB Output is correct
8 Correct 48 ms 125516 KB Output is correct
9 Correct 51 ms 125516 KB Output is correct
10 Correct 50 ms 125556 KB Output is correct
11 Correct 51 ms 125644 KB Output is correct
12 Correct 49 ms 125564 KB Output is correct
13 Correct 48 ms 125520 KB Output is correct
14 Correct 53 ms 125632 KB Output is correct
15 Correct 49 ms 125520 KB Output is correct
16 Correct 48 ms 125596 KB Output is correct
17 Correct 54 ms 126064 KB Output is correct
18 Correct 54 ms 125964 KB Output is correct
19 Correct 55 ms 126040 KB Output is correct
20 Correct 53 ms 125896 KB Output is correct
21 Correct 55 ms 125992 KB Output is correct
22 Correct 54 ms 125964 KB Output is correct
23 Correct 60 ms 125960 KB Output is correct
24 Correct 410 ms 146984 KB Output is correct
25 Correct 427 ms 149268 KB Output is correct
26 Correct 398 ms 146984 KB Output is correct
27 Correct 441 ms 149404 KB Output is correct
28 Correct 495 ms 147596 KB Output is correct
29 Correct 404 ms 146900 KB Output is correct
30 Correct 849 ms 151348 KB Output is correct
31 Correct 123 ms 136560 KB Output is correct
32 Correct 314 ms 138844 KB Output is correct
33 Correct 534 ms 146592 KB Output is correct
34 Correct 772 ms 150300 KB Output is correct
35 Correct 830 ms 151240 KB Output is correct
36 Correct 770 ms 150888 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125556 KB Output is correct
2 Correct 50 ms 125596 KB Output is correct
3 Correct 53 ms 125532 KB Output is correct
4 Correct 53 ms 125520 KB Output is correct
5 Correct 52 ms 125516 KB Output is correct
6 Correct 49 ms 125512 KB Output is correct
7 Correct 49 ms 125596 KB Output is correct
8 Correct 48 ms 125516 KB Output is correct
9 Correct 51 ms 125516 KB Output is correct
10 Correct 50 ms 125556 KB Output is correct
11 Correct 51 ms 125644 KB Output is correct
12 Correct 49 ms 125564 KB Output is correct
13 Correct 48 ms 125520 KB Output is correct
14 Correct 53 ms 125632 KB Output is correct
15 Correct 49 ms 125520 KB Output is correct
16 Correct 48 ms 125596 KB Output is correct
17 Correct 54 ms 126064 KB Output is correct
18 Correct 54 ms 125964 KB Output is correct
19 Correct 55 ms 126040 KB Output is correct
20 Correct 53 ms 125896 KB Output is correct
21 Correct 55 ms 125992 KB Output is correct
22 Correct 54 ms 125964 KB Output is correct
23 Correct 60 ms 125960 KB Output is correct
24 Correct 410 ms 146984 KB Output is correct
25 Correct 427 ms 149268 KB Output is correct
26 Correct 398 ms 146984 KB Output is correct
27 Correct 441 ms 149404 KB Output is correct
28 Correct 495 ms 147596 KB Output is correct
29 Correct 404 ms 146900 KB Output is correct
30 Correct 849 ms 151348 KB Output is correct
31 Correct 123 ms 136560 KB Output is correct
32 Correct 314 ms 138844 KB Output is correct
33 Correct 534 ms 146592 KB Output is correct
34 Correct 772 ms 150300 KB Output is correct
35 Correct 830 ms 151240 KB Output is correct
36 Correct 770 ms 150888 KB Output is correct
37 Correct 442 ms 146924 KB Output is correct
38 Correct 487 ms 149312 KB Output is correct
39 Correct 433 ms 146896 KB Output is correct
40 Correct 432 ms 147008 KB Output is correct
41 Correct 50 ms 125628 KB Output is correct
42 Correct 868 ms 151340 KB Output is correct
43 Correct 531 ms 146556 KB Output is correct
44 Correct 775 ms 150268 KB Output is correct
45 Correct 820 ms 151496 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 125556 KB Output is correct
2 Correct 50 ms 125596 KB Output is correct
3 Correct 53 ms 125532 KB Output is correct
4 Correct 53 ms 125520 KB Output is correct
5 Correct 52 ms 125516 KB Output is correct
6 Correct 49 ms 125512 KB Output is correct
7 Correct 49 ms 125596 KB Output is correct
8 Correct 48 ms 125516 KB Output is correct
9 Correct 51 ms 125516 KB Output is correct
10 Correct 50 ms 125556 KB Output is correct
11 Correct 51 ms 125644 KB Output is correct
12 Correct 49 ms 125564 KB Output is correct
13 Correct 48 ms 125520 KB Output is correct
14 Correct 53 ms 125632 KB Output is correct
15 Correct 49 ms 125520 KB Output is correct
16 Correct 48 ms 125596 KB Output is correct
17 Correct 54 ms 126064 KB Output is correct
18 Correct 54 ms 125964 KB Output is correct
19 Correct 55 ms 126040 KB Output is correct
20 Correct 53 ms 125896 KB Output is correct
21 Correct 55 ms 125992 KB Output is correct
22 Correct 54 ms 125964 KB Output is correct
23 Correct 60 ms 125960 KB Output is correct
24 Correct 410 ms 146984 KB Output is correct
25 Correct 427 ms 149268 KB Output is correct
26 Correct 398 ms 146984 KB Output is correct
27 Correct 441 ms 149404 KB Output is correct
28 Correct 495 ms 147596 KB Output is correct
29 Correct 404 ms 146900 KB Output is correct
30 Correct 849 ms 151348 KB Output is correct
31 Correct 123 ms 136560 KB Output is correct
32 Correct 314 ms 138844 KB Output is correct
33 Correct 534 ms 146592 KB Output is correct
34 Correct 772 ms 150300 KB Output is correct
35 Correct 830 ms 151240 KB Output is correct
36 Correct 770 ms 150888 KB Output is correct
37 Correct 442 ms 146924 KB Output is correct
38 Correct 487 ms 149312 KB Output is correct
39 Correct 433 ms 146896 KB Output is correct
40 Correct 432 ms 147008 KB Output is correct
41 Correct 50 ms 125628 KB Output is correct
42 Correct 868 ms 151340 KB Output is correct
43 Correct 531 ms 146556 KB Output is correct
44 Correct 775 ms 150268 KB Output is correct
45 Correct 820 ms 151496 KB Output is correct
46 Correct 2217 ms 228608 KB Output is correct
47 Correct 2280 ms 239968 KB Output is correct
48 Correct 2107 ms 228252 KB Output is correct
49 Correct 2079 ms 228304 KB Output is correct
50 Correct 5253 ms 251732 KB Output is correct
51 Correct 2902 ms 225272 KB Output is correct
52 Correct 4120 ms 241764 KB Output is correct
53 Correct 4861 ms 250336 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 147928 KB Output is correct
2 Correct 449 ms 147884 KB Output is correct
3 Correct 423 ms 146948 KB Output is correct
4 Correct 344 ms 145164 KB Output is correct
5 Correct 49 ms 125532 KB Output is correct
6 Correct 461 ms 147164 KB Output is correct
7 Correct 127 ms 134224 KB Output is correct
8 Correct 318 ms 139116 KB Output is correct
9 Correct 440 ms 147028 KB Output is correct
10 Correct 406 ms 146968 KB Output is correct
11 Correct 386 ms 147004 KB Output is correct
12 Correct 50 ms 125556 KB Output is correct
13 Correct 50 ms 125596 KB Output is correct
14 Correct 53 ms 125532 KB Output is correct
15 Correct 53 ms 125520 KB Output is correct
16 Correct 52 ms 125516 KB Output is correct
17 Correct 49 ms 125512 KB Output is correct
18 Correct 49 ms 125596 KB Output is correct
19 Correct 48 ms 125516 KB Output is correct
20 Correct 51 ms 125516 KB Output is correct
21 Correct 50 ms 125556 KB Output is correct
22 Correct 51 ms 125644 KB Output is correct
23 Correct 49 ms 125564 KB Output is correct
24 Correct 48 ms 125520 KB Output is correct
25 Correct 53 ms 125632 KB Output is correct
26 Correct 49 ms 125520 KB Output is correct
27 Correct 48 ms 125596 KB Output is correct
28 Correct 54 ms 126064 KB Output is correct
29 Correct 54 ms 125964 KB Output is correct
30 Correct 55 ms 126040 KB Output is correct
31 Correct 53 ms 125896 KB Output is correct
32 Correct 55 ms 125992 KB Output is correct
33 Correct 54 ms 125964 KB Output is correct
34 Correct 60 ms 125960 KB Output is correct
35 Correct 410 ms 146984 KB Output is correct
36 Correct 427 ms 149268 KB Output is correct
37 Correct 398 ms 146984 KB Output is correct
38 Correct 441 ms 149404 KB Output is correct
39 Correct 495 ms 147596 KB Output is correct
40 Correct 404 ms 146900 KB Output is correct
41 Correct 849 ms 151348 KB Output is correct
42 Correct 123 ms 136560 KB Output is correct
43 Correct 314 ms 138844 KB Output is correct
44 Correct 534 ms 146592 KB Output is correct
45 Correct 772 ms 150300 KB Output is correct
46 Correct 830 ms 151240 KB Output is correct
47 Correct 770 ms 150888 KB Output is correct
48 Correct 442 ms 146924 KB Output is correct
49 Correct 487 ms 149312 KB Output is correct
50 Correct 433 ms 146896 KB Output is correct
51 Correct 432 ms 147008 KB Output is correct
52 Correct 50 ms 125628 KB Output is correct
53 Correct 868 ms 151340 KB Output is correct
54 Correct 531 ms 146556 KB Output is correct
55 Correct 775 ms 150268 KB Output is correct
56 Correct 820 ms 151496 KB Output is correct
57 Correct 422 ms 147332 KB Output is correct
58 Correct 466 ms 149660 KB Output is correct
59 Correct 431 ms 146648 KB Output is correct
60 Correct 437 ms 146648 KB Output is correct
61 Correct 822 ms 151324 KB Output is correct
62 Correct 52 ms 125632 KB Output is correct
63 Correct 865 ms 151068 KB Output is correct
64 Correct 545 ms 159180 KB Output is correct
65 Correct 759 ms 162720 KB Output is correct
66 Correct 830 ms 157864 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 147928 KB Output is correct
2 Correct 449 ms 147884 KB Output is correct
3 Correct 423 ms 146948 KB Output is correct
4 Correct 344 ms 145164 KB Output is correct
5 Correct 49 ms 125532 KB Output is correct
6 Correct 461 ms 147164 KB Output is correct
7 Correct 127 ms 134224 KB Output is correct
8 Correct 318 ms 139116 KB Output is correct
9 Correct 440 ms 147028 KB Output is correct
10 Correct 406 ms 146968 KB Output is correct
11 Correct 386 ms 147004 KB Output is correct
12 Correct 50 ms 125556 KB Output is correct
13 Correct 50 ms 125596 KB Output is correct
14 Correct 53 ms 125532 KB Output is correct
15 Correct 53 ms 125520 KB Output is correct
16 Correct 52 ms 125516 KB Output is correct
17 Correct 49 ms 125512 KB Output is correct
18 Correct 49 ms 125596 KB Output is correct
19 Correct 48 ms 125516 KB Output is correct
20 Correct 51 ms 125516 KB Output is correct
21 Correct 50 ms 125556 KB Output is correct
22 Correct 51 ms 125644 KB Output is correct
23 Correct 49 ms 125564 KB Output is correct
24 Correct 48 ms 125520 KB Output is correct
25 Correct 53 ms 125632 KB Output is correct
26 Correct 49 ms 125520 KB Output is correct
27 Correct 48 ms 125596 KB Output is correct
28 Correct 54 ms 126064 KB Output is correct
29 Correct 54 ms 125964 KB Output is correct
30 Correct 55 ms 126040 KB Output is correct
31 Correct 53 ms 125896 KB Output is correct
32 Correct 55 ms 125992 KB Output is correct
33 Correct 54 ms 125964 KB Output is correct
34 Correct 60 ms 125960 KB Output is correct
35 Correct 410 ms 146984 KB Output is correct
36 Correct 427 ms 149268 KB Output is correct
37 Correct 398 ms 146984 KB Output is correct
38 Correct 441 ms 149404 KB Output is correct
39 Correct 495 ms 147596 KB Output is correct
40 Correct 404 ms 146900 KB Output is correct
41 Correct 849 ms 151348 KB Output is correct
42 Correct 123 ms 136560 KB Output is correct
43 Correct 314 ms 138844 KB Output is correct
44 Correct 534 ms 146592 KB Output is correct
45 Correct 772 ms 150300 KB Output is correct
46 Correct 830 ms 151240 KB Output is correct
47 Correct 770 ms 150888 KB Output is correct
48 Correct 442 ms 146924 KB Output is correct
49 Correct 487 ms 149312 KB Output is correct
50 Correct 433 ms 146896 KB Output is correct
51 Correct 432 ms 147008 KB Output is correct
52 Correct 50 ms 125628 KB Output is correct
53 Correct 868 ms 151340 KB Output is correct
54 Correct 531 ms 146556 KB Output is correct
55 Correct 775 ms 150268 KB Output is correct
56 Correct 820 ms 151496 KB Output is correct
57 Correct 2217 ms 228608 KB Output is correct
58 Correct 2280 ms 239968 KB Output is correct
59 Correct 2107 ms 228252 KB Output is correct
60 Correct 2079 ms 228304 KB Output is correct
61 Correct 5253 ms 251732 KB Output is correct
62 Correct 2902 ms 225272 KB Output is correct
63 Correct 4120 ms 241764 KB Output is correct
64 Correct 4861 ms 250336 KB Output is correct
65 Correct 422 ms 147332 KB Output is correct
66 Correct 466 ms 149660 KB Output is correct
67 Correct 431 ms 146648 KB Output is correct
68 Correct 437 ms 146648 KB Output is correct
69 Correct 822 ms 151324 KB Output is correct
70 Correct 52 ms 125632 KB Output is correct
71 Correct 865 ms 151068 KB Output is correct
72 Correct 545 ms 159180 KB Output is correct
73 Correct 759 ms 162720 KB Output is correct
74 Correct 830 ms 157864 KB Output is correct
75 Correct 2113 ms 299172 KB Output is correct
76 Correct 2266 ms 310812 KB Output is correct
77 Correct 2164 ms 286132 KB Output is correct
78 Correct 2166 ms 286292 KB Output is correct
79 Correct 5433 ms 319520 KB Output is correct
80 Correct 3289 ms 291520 KB Output is correct
81 Correct 4170 ms 302636 KB Output is correct
82 Correct 4989 ms 287704 KB Output is correct
83 Correct 5049 ms 306204 KB Output is correct