oj.uz

Submission #709441

# Submission time Handle Problem Language Result Execution time Memory
709441 2023-03-13T15:19:48 Z PixelCat Two Dishes (JOI19_dishes) C++14
74 / 100
 3981 ms 229588 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].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));
        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] = 1;
        pr1[i] = pr1[i - 1] + a1[i];
    }
    For(i, 1, m) {
        a2[i] = rng() % 10 + 1;
        s2[i] = rng() % 100 + 1;
        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(p2[i] < 0 && t2[i] < n && t2[i] >= 0) v.eb(pii(i - 1, t2[i] + 1), 0);
    }

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

            if(owo) {
                seg2.add(0, 0, n, i, n, -p1[i]);
                seg.add(0, 0, n, i, n, p1[i]);
            }
            
            int val = seg.ask(0, 0, n, 0, i - 1) + seg2.ask(0, 0, n, i, i);
            if(it <= t1[i]) val += p1[i];
            seg.set(0, 0, n, i, val - seg2.ask(0, 0, n, i, i));
        }
    }
    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 395 ms 148484 KB Output is correct
2 Correct 410 ms 148520 KB Output is correct
3 Correct 369 ms 148908 KB Output is correct
4 Correct 337 ms 146948 KB Output is correct
5 Correct 52 ms 125636 KB Output is correct
6 Correct 408 ms 148144 KB Output is correct
7 Correct 122 ms 136280 KB Output is correct
8 Correct 305 ms 141076 KB Output is correct
9 Correct 382 ms 148864 KB Output is correct
10 Correct 369 ms 148908 KB Output is correct
11 Correct 331 ms 148880 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 125604 KB Output is correct
3 Correct 53 ms 125636 KB Output is correct
4 Correct 51 ms 125596 KB Output is correct
5 Correct 47 ms 125520 KB Output is correct
6 Correct 47 ms 125604 KB Output is correct
7 Correct 48 ms 125508 KB Output is correct
8 Correct 52 ms 125528 KB Output is correct
9 Correct 47 ms 125568 KB Output is correct
10 Correct 46 ms 125516 KB Output is correct
11 Correct 48 ms 125640 KB Output is correct
12 Correct 50 ms 125644 KB Output is correct
13 Correct 46 ms 125572 KB Output is correct
14 Correct 46 ms 125628 KB Output is correct
15 Correct 48 ms 125520 KB Output is correct
16 Correct 47 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 125604 KB Output is correct
3 Correct 53 ms 125636 KB Output is correct
4 Correct 51 ms 125596 KB Output is correct
5 Correct 47 ms 125520 KB Output is correct
6 Correct 47 ms 125604 KB Output is correct
7 Correct 48 ms 125508 KB Output is correct
8 Correct 52 ms 125528 KB Output is correct
9 Correct 47 ms 125568 KB Output is correct
10 Correct 46 ms 125516 KB Output is correct
11 Correct 48 ms 125640 KB Output is correct
12 Correct 50 ms 125644 KB Output is correct
13 Correct 46 ms 125572 KB Output is correct
14 Correct 46 ms 125628 KB Output is correct
15 Correct 48 ms 125520 KB Output is correct
16 Correct 47 ms 125588 KB Output is correct
17 Correct 50 ms 125992 KB Output is correct
18 Correct 48 ms 125852 KB Output is correct
19 Correct 52 ms 125936 KB Output is correct
20 Correct 50 ms 125924 KB Output is correct
21 Correct 51 ms 125992 KB Output is correct
22 Correct 51 ms 125832 KB Output is correct
23 Correct 52 ms 125844 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 125604 KB Output is correct
3 Correct 53 ms 125636 KB Output is correct
4 Correct 51 ms 125596 KB Output is correct
5 Correct 47 ms 125520 KB Output is correct
6 Correct 47 ms 125604 KB Output is correct
7 Correct 48 ms 125508 KB Output is correct
8 Correct 52 ms 125528 KB Output is correct
9 Correct 47 ms 125568 KB Output is correct
10 Correct 46 ms 125516 KB Output is correct
11 Correct 48 ms 125640 KB Output is correct
12 Correct 50 ms 125644 KB Output is correct
13 Correct 46 ms 125572 KB Output is correct
14 Correct 46 ms 125628 KB Output is correct
15 Correct 48 ms 125520 KB Output is correct
16 Correct 47 ms 125588 KB Output is correct
17 Correct 50 ms 125992 KB Output is correct
18 Correct 48 ms 125852 KB Output is correct
19 Correct 52 ms 125936 KB Output is correct
20 Correct 50 ms 125924 KB Output is correct
21 Correct 51 ms 125992 KB Output is correct
22 Correct 51 ms 125832 KB Output is correct
23 Correct 52 ms 125844 KB Output is correct
24 Correct 348 ms 148972 KB Output is correct
25 Correct 290 ms 146508 KB Output is correct
26 Correct 362 ms 148956 KB Output is correct
27 Correct 297 ms 146480 KB Output is correct
28 Correct 418 ms 148216 KB Output is correct
29 Correct 344 ms 148736 KB Output is correct
30 Correct 633 ms 148860 KB Output is correct
31 Correct 111 ms 136132 KB Output is correct
32 Correct 299 ms 140944 KB Output is correct
33 Correct 402 ms 146136 KB Output is correct
34 Correct 580 ms 148464 KB Output is correct
35 Correct 605 ms 148780 KB Output is correct
36 Correct 573 ms 148536 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 125604 KB Output is correct
3 Correct 53 ms 125636 KB Output is correct
4 Correct 51 ms 125596 KB Output is correct
5 Correct 47 ms 125520 KB Output is correct
6 Correct 47 ms 125604 KB Output is correct
7 Correct 48 ms 125508 KB Output is correct
8 Correct 52 ms 125528 KB Output is correct
9 Correct 47 ms 125568 KB Output is correct
10 Correct 46 ms 125516 KB Output is correct
11 Correct 48 ms 125640 KB Output is correct
12 Correct 50 ms 125644 KB Output is correct
13 Correct 46 ms 125572 KB Output is correct
14 Correct 46 ms 125628 KB Output is correct
15 Correct 48 ms 125520 KB Output is correct
16 Correct 47 ms 125588 KB Output is correct
17 Correct 50 ms 125992 KB Output is correct
18 Correct 48 ms 125852 KB Output is correct
19 Correct 52 ms 125936 KB Output is correct
20 Correct 50 ms 125924 KB Output is correct
21 Correct 51 ms 125992 KB Output is correct
22 Correct 51 ms 125832 KB Output is correct
23 Correct 52 ms 125844 KB Output is correct
24 Correct 348 ms 148972 KB Output is correct
25 Correct 290 ms 146508 KB Output is correct
26 Correct 362 ms 148956 KB Output is correct
27 Correct 297 ms 146480 KB Output is correct
28 Correct 418 ms 148216 KB Output is correct
29 Correct 344 ms 148736 KB Output is correct
30 Correct 633 ms 148860 KB Output is correct
31 Correct 111 ms 136132 KB Output is correct
32 Correct 299 ms 140944 KB Output is correct
33 Correct 402 ms 146136 KB Output is correct
34 Correct 580 ms 148464 KB Output is correct
35 Correct 605 ms 148780 KB Output is correct
36 Correct 573 ms 148536 KB Output is correct
37 Correct 393 ms 148828 KB Output is correct
38 Correct 324 ms 146412 KB Output is correct
39 Correct 387 ms 148688 KB Output is correct
40 Correct 402 ms 148672 KB Output is correct
41 Correct 50 ms 125536 KB Output is correct
42 Correct 658 ms 148636 KB Output is correct
43 Correct 413 ms 146064 KB Output is correct
44 Correct 610 ms 148368 KB Output is correct
45 Correct 637 ms 148540 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 125604 KB Output is correct
3 Correct 53 ms 125636 KB Output is correct
4 Correct 51 ms 125596 KB Output is correct
5 Correct 47 ms 125520 KB Output is correct
6 Correct 47 ms 125604 KB Output is correct
7 Correct 48 ms 125508 KB Output is correct
8 Correct 52 ms 125528 KB Output is correct
9 Correct 47 ms 125568 KB Output is correct
10 Correct 46 ms 125516 KB Output is correct
11 Correct 48 ms 125640 KB Output is correct
12 Correct 50 ms 125644 KB Output is correct
13 Correct 46 ms 125572 KB Output is correct
14 Correct 46 ms 125628 KB Output is correct
15 Correct 48 ms 125520 KB Output is correct
16 Correct 47 ms 125588 KB Output is correct
17 Correct 50 ms 125992 KB Output is correct
18 Correct 48 ms 125852 KB Output is correct
19 Correct 52 ms 125936 KB Output is correct
20 Correct 50 ms 125924 KB Output is correct
21 Correct 51 ms 125992 KB Output is correct
22 Correct 51 ms 125832 KB Output is correct
23 Correct 52 ms 125844 KB Output is correct
24 Correct 348 ms 148972 KB Output is correct
25 Correct 290 ms 146508 KB Output is correct
26 Correct 362 ms 148956 KB Output is correct
27 Correct 297 ms 146480 KB Output is correct
28 Correct 418 ms 148216 KB Output is correct
29 Correct 344 ms 148736 KB Output is correct
30 Correct 633 ms 148860 KB Output is correct
31 Correct 111 ms 136132 KB Output is correct
32 Correct 299 ms 140944 KB Output is correct
33 Correct 402 ms 146136 KB Output is correct
34 Correct 580 ms 148464 KB Output is correct
35 Correct 605 ms 148780 KB Output is correct
36 Correct 573 ms 148536 KB Output is correct
37 Correct 393 ms 148828 KB Output is correct
38 Correct 324 ms 146412 KB Output is correct
39 Correct 387 ms 148688 KB Output is correct
40 Correct 402 ms 148672 KB Output is correct
41 Correct 50 ms 125536 KB Output is correct
42 Correct 658 ms 148636 KB Output is correct
43 Correct 413 ms 146064 KB Output is correct
44 Correct 610 ms 148368 KB Output is correct
45 Correct 637 ms 148540 KB Output is correct
46 Correct 1891 ms 227660 KB Output is correct
47 Correct 1479 ms 217896 KB Output is correct
48 Correct 1870 ms 229588 KB Output is correct
49 Correct 1832 ms 229020 KB Output is correct
50 Correct 3981 ms 228672 KB Output is correct
51 Correct 2300 ms 213880 KB Output is correct
52 Correct 3024 ms 224012 KB Output is correct
53 Correct 3657 ms 226908 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 148484 KB Output is correct
2 Correct 410 ms 148520 KB Output is correct
3 Correct 369 ms 148908 KB Output is correct
4 Correct 337 ms 146948 KB Output is correct
5 Correct 52 ms 125636 KB Output is correct
6 Correct 408 ms 148144 KB Output is correct
7 Correct 122 ms 136280 KB Output is correct
8 Correct 305 ms 141076 KB Output is correct
9 Correct 382 ms 148864 KB Output is correct
10 Correct 369 ms 148908 KB Output is correct
11 Correct 331 ms 148880 KB Output is correct
12 Correct 48 ms 125516 KB Output is correct
13 Correct 49 ms 125604 KB Output is correct
14 Correct 53 ms 125636 KB Output is correct
15 Correct 51 ms 125596 KB Output is correct
16 Correct 47 ms 125520 KB Output is correct
17 Correct 47 ms 125604 KB Output is correct
18 Correct 48 ms 125508 KB Output is correct
19 Correct 52 ms 125528 KB Output is correct
20 Correct 47 ms 125568 KB Output is correct
21 Correct 46 ms 125516 KB Output is correct
22 Correct 48 ms 125640 KB Output is correct
23 Correct 50 ms 125644 KB Output is correct
24 Correct 46 ms 125572 KB Output is correct
25 Correct 46 ms 125628 KB Output is correct
26 Correct 48 ms 125520 KB Output is correct
27 Correct 47 ms 125588 KB Output is correct
28 Correct 50 ms 125992 KB Output is correct
29 Correct 48 ms 125852 KB Output is correct
30 Correct 52 ms 125936 KB Output is correct
31 Correct 50 ms 125924 KB Output is correct
32 Correct 51 ms 125992 KB Output is correct
33 Correct 51 ms 125832 KB Output is correct
34 Correct 52 ms 125844 KB Output is correct
35 Correct 348 ms 148972 KB Output is correct
36 Correct 290 ms 146508 KB Output is correct
37 Correct 362 ms 148956 KB Output is correct
38 Correct 297 ms 146480 KB Output is correct
39 Correct 418 ms 148216 KB Output is correct
40 Correct 344 ms 148736 KB Output is correct
41 Correct 633 ms 148860 KB Output is correct
42 Correct 111 ms 136132 KB Output is correct
43 Correct 299 ms 140944 KB Output is correct
44 Correct 402 ms 146136 KB Output is correct
45 Correct 580 ms 148464 KB Output is correct
46 Correct 605 ms 148780 KB Output is correct
47 Correct 573 ms 148536 KB Output is correct
48 Correct 393 ms 148828 KB Output is correct
49 Correct 324 ms 146412 KB Output is correct
50 Correct 387 ms 148688 KB Output is correct
51 Correct 402 ms 148672 KB Output is correct
52 Correct 50 ms 125536 KB Output is correct
53 Correct 658 ms 148636 KB Output is correct
54 Correct 413 ms 146064 KB Output is correct
55 Correct 610 ms 148368 KB Output is correct
56 Correct 637 ms 148540 KB Output is correct
57 Correct 386 ms 146604 KB Output is correct
58 Incorrect 410 ms 149096 KB Output isn't correct
59 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 148484 KB Output is correct
2 Correct 410 ms 148520 KB Output is correct
3 Correct 369 ms 148908 KB Output is correct
4 Correct 337 ms 146948 KB Output is correct
5 Correct 52 ms 125636 KB Output is correct
6 Correct 408 ms 148144 KB Output is correct
7 Correct 122 ms 136280 KB Output is correct
8 Correct 305 ms 141076 KB Output is correct
9 Correct 382 ms 148864 KB Output is correct
10 Correct 369 ms 148908 KB Output is correct
11 Correct 331 ms 148880 KB Output is correct
12 Correct 48 ms 125516 KB Output is correct
13 Correct 49 ms 125604 KB Output is correct
14 Correct 53 ms 125636 KB Output is correct
15 Correct 51 ms 125596 KB Output is correct
16 Correct 47 ms 125520 KB Output is correct
17 Correct 47 ms 125604 KB Output is correct
18 Correct 48 ms 125508 KB Output is correct
19 Correct 52 ms 125528 KB Output is correct
20 Correct 47 ms 125568 KB Output is correct
21 Correct 46 ms 125516 KB Output is correct
22 Correct 48 ms 125640 KB Output is correct
23 Correct 50 ms 125644 KB Output is correct
24 Correct 46 ms 125572 KB Output is correct
25 Correct 46 ms 125628 KB Output is correct
26 Correct 48 ms 125520 KB Output is correct
27 Correct 47 ms 125588 KB Output is correct
28 Correct 50 ms 125992 KB Output is correct
29 Correct 48 ms 125852 KB Output is correct
30 Correct 52 ms 125936 KB Output is correct
31 Correct 50 ms 125924 KB Output is correct
32 Correct 51 ms 125992 KB Output is correct
33 Correct 51 ms 125832 KB Output is correct
34 Correct 52 ms 125844 KB Output is correct
35 Correct 348 ms 148972 KB Output is correct
36 Correct 290 ms 146508 KB Output is correct
37 Correct 362 ms 148956 KB Output is correct
38 Correct 297 ms 146480 KB Output is correct
39 Correct 418 ms 148216 KB Output is correct
40 Correct 344 ms 148736 KB Output is correct
41 Correct 633 ms 148860 KB Output is correct
42 Correct 111 ms 136132 KB Output is correct
43 Correct 299 ms 140944 KB Output is correct
44 Correct 402 ms 146136 KB Output is correct
45 Correct 580 ms 148464 KB Output is correct
46 Correct 605 ms 148780 KB Output is correct
47 Correct 573 ms 148536 KB Output is correct
48 Correct 393 ms 148828 KB Output is correct
49 Correct 324 ms 146412 KB Output is correct
50 Correct 387 ms 148688 KB Output is correct
51 Correct 402 ms 148672 KB Output is correct
52 Correct 50 ms 125536 KB Output is correct
53 Correct 658 ms 148636 KB Output is correct
54 Correct 413 ms 146064 KB Output is correct
55 Correct 610 ms 148368 KB Output is correct
56 Correct 637 ms 148540 KB Output is correct
57 Correct 1891 ms 227660 KB Output is correct
58 Correct 1479 ms 217896 KB Output is correct
59 Correct 1870 ms 229588 KB Output is correct
60 Correct 1832 ms 229020 KB Output is correct
61 Correct 3981 ms 228672 KB Output is correct
62 Correct 2300 ms 213880 KB Output is correct
63 Correct 3024 ms 224012 KB Output is correct
64 Correct 3657 ms 226908 KB Output is correct
65 Correct 386 ms 146604 KB Output is correct
66 Incorrect 410 ms 149096 KB Output isn't correct
67 Halted 0 ms 0 KB -