oj.uz

Submission #709467

# Submission time Handle Problem Language Result Execution time Memory
709467 2023-03-13T16:10:20 Z PixelCat Two Dishes (JOI19_dishes) C++14
74 / 100
 5957 ms 250292 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);
            val = max(val, seg.ask(0, 0, n, i, i) + 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]);
            }
            
            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 565 ms 150020 KB Output is correct
2 Correct 529 ms 150148 KB Output is correct
3 Correct 449 ms 149128 KB Output is correct
4 Correct 440 ms 146952 KB Output is correct
5 Correct 49 ms 125564 KB Output is correct
6 Correct 518 ms 149160 KB Output is correct
7 Correct 125 ms 136728 KB Output is correct
8 Correct 390 ms 141520 KB Output is correct
9 Correct 470 ms 148984 KB Output is correct
10 Correct 438 ms 149320 KB Output is correct
11 Correct 398 ms 149344 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125584 KB Output is correct
2 Correct 53 ms 125592 KB Output is correct
3 Correct 49 ms 125628 KB Output is correct
4 Correct 49 ms 125648 KB Output is correct
5 Correct 51 ms 125516 KB Output is correct
6 Correct 52 ms 125572 KB Output is correct
7 Correct 50 ms 125564 KB Output is correct
8 Correct 50 ms 125524 KB Output is correct
9 Correct 61 ms 125596 KB Output is correct
10 Correct 49 ms 125596 KB Output is correct
11 Correct 49 ms 125564 KB Output is correct
12 Correct 48 ms 125584 KB Output is correct
13 Correct 48 ms 125516 KB Output is correct
14 Correct 50 ms 125616 KB Output is correct
15 Correct 51 ms 125624 KB Output is correct
16 Correct 52 ms 125544 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125584 KB Output is correct
2 Correct 53 ms 125592 KB Output is correct
3 Correct 49 ms 125628 KB Output is correct
4 Correct 49 ms 125648 KB Output is correct
5 Correct 51 ms 125516 KB Output is correct
6 Correct 52 ms 125572 KB Output is correct
7 Correct 50 ms 125564 KB Output is correct
8 Correct 50 ms 125524 KB Output is correct
9 Correct 61 ms 125596 KB Output is correct
10 Correct 49 ms 125596 KB Output is correct
11 Correct 49 ms 125564 KB Output is correct
12 Correct 48 ms 125584 KB Output is correct
13 Correct 48 ms 125516 KB Output is correct
14 Correct 50 ms 125616 KB Output is correct
15 Correct 51 ms 125624 KB Output is correct
16 Correct 52 ms 125544 KB Output is correct
17 Correct 58 ms 125900 KB Output is correct
18 Correct 53 ms 126068 KB Output is correct
19 Correct 52 ms 126060 KB Output is correct
20 Correct 54 ms 125900 KB Output is correct
21 Correct 54 ms 126064 KB Output is correct
22 Correct 60 ms 125948 KB Output is correct
23 Correct 55 ms 125932 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125584 KB Output is correct
2 Correct 53 ms 125592 KB Output is correct
3 Correct 49 ms 125628 KB Output is correct
4 Correct 49 ms 125648 KB Output is correct
5 Correct 51 ms 125516 KB Output is correct
6 Correct 52 ms 125572 KB Output is correct
7 Correct 50 ms 125564 KB Output is correct
8 Correct 50 ms 125524 KB Output is correct
9 Correct 61 ms 125596 KB Output is correct
10 Correct 49 ms 125596 KB Output is correct
11 Correct 49 ms 125564 KB Output is correct
12 Correct 48 ms 125584 KB Output is correct
13 Correct 48 ms 125516 KB Output is correct
14 Correct 50 ms 125616 KB Output is correct
15 Correct 51 ms 125624 KB Output is correct
16 Correct 52 ms 125544 KB Output is correct
17 Correct 58 ms 125900 KB Output is correct
18 Correct 53 ms 126068 KB Output is correct
19 Correct 52 ms 126060 KB Output is correct
20 Correct 54 ms 125900 KB Output is correct
21 Correct 54 ms 126064 KB Output is correct
22 Correct 60 ms 125948 KB Output is correct
23 Correct 55 ms 125932 KB Output is correct
24 Correct 439 ms 149116 KB Output is correct
25 Correct 494 ms 151560 KB Output is correct
26 Correct 443 ms 149168 KB Output is correct
27 Correct 504 ms 151504 KB Output is correct
28 Correct 573 ms 149740 KB Output is correct
29 Correct 451 ms 149072 KB Output is correct
30 Correct 983 ms 153556 KB Output is correct
31 Correct 135 ms 139172 KB Output is correct
32 Correct 402 ms 141384 KB Output is correct
33 Correct 626 ms 148692 KB Output is correct
34 Correct 973 ms 152208 KB Output is correct
35 Correct 1136 ms 152912 KB Output is correct
36 Correct 1149 ms 152636 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125584 KB Output is correct
2 Correct 53 ms 125592 KB Output is correct
3 Correct 49 ms 125628 KB Output is correct
4 Correct 49 ms 125648 KB Output is correct
5 Correct 51 ms 125516 KB Output is correct
6 Correct 52 ms 125572 KB Output is correct
7 Correct 50 ms 125564 KB Output is correct
8 Correct 50 ms 125524 KB Output is correct
9 Correct 61 ms 125596 KB Output is correct
10 Correct 49 ms 125596 KB Output is correct
11 Correct 49 ms 125564 KB Output is correct
12 Correct 48 ms 125584 KB Output is correct
13 Correct 48 ms 125516 KB Output is correct
14 Correct 50 ms 125616 KB Output is correct
15 Correct 51 ms 125624 KB Output is correct
16 Correct 52 ms 125544 KB Output is correct
17 Correct 58 ms 125900 KB Output is correct
18 Correct 53 ms 126068 KB Output is correct
19 Correct 52 ms 126060 KB Output is correct
20 Correct 54 ms 125900 KB Output is correct
21 Correct 54 ms 126064 KB Output is correct
22 Correct 60 ms 125948 KB Output is correct
23 Correct 55 ms 125932 KB Output is correct
24 Correct 439 ms 149116 KB Output is correct
25 Correct 494 ms 151560 KB Output is correct
26 Correct 443 ms 149168 KB Output is correct
27 Correct 504 ms 151504 KB Output is correct
28 Correct 573 ms 149740 KB Output is correct
29 Correct 451 ms 149072 KB Output is correct
30 Correct 983 ms 153556 KB Output is correct
31 Correct 135 ms 139172 KB Output is correct
32 Correct 402 ms 141384 KB Output is correct
33 Correct 626 ms 148692 KB Output is correct
34 Correct 973 ms 152208 KB Output is correct
35 Correct 1136 ms 152912 KB Output is correct
36 Correct 1149 ms 152636 KB Output is correct
37 Correct 552 ms 148080 KB Output is correct
38 Correct 666 ms 150468 KB Output is correct
39 Correct 494 ms 148236 KB Output is correct
40 Correct 459 ms 147948 KB Output is correct
41 Correct 49 ms 125564 KB Output is correct
42 Correct 998 ms 152324 KB Output is correct
43 Correct 580 ms 147348 KB Output is correct
44 Correct 893 ms 151028 KB Output is correct
45 Correct 984 ms 152568 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 125584 KB Output is correct
2 Correct 53 ms 125592 KB Output is correct
3 Correct 49 ms 125628 KB Output is correct
4 Correct 49 ms 125648 KB Output is correct
5 Correct 51 ms 125516 KB Output is correct
6 Correct 52 ms 125572 KB Output is correct
7 Correct 50 ms 125564 KB Output is correct
8 Correct 50 ms 125524 KB Output is correct
9 Correct 61 ms 125596 KB Output is correct
10 Correct 49 ms 125596 KB Output is correct
11 Correct 49 ms 125564 KB Output is correct
12 Correct 48 ms 125584 KB Output is correct
13 Correct 48 ms 125516 KB Output is correct
14 Correct 50 ms 125616 KB Output is correct
15 Correct 51 ms 125624 KB Output is correct
16 Correct 52 ms 125544 KB Output is correct
17 Correct 58 ms 125900 KB Output is correct
18 Correct 53 ms 126068 KB Output is correct
19 Correct 52 ms 126060 KB Output is correct
20 Correct 54 ms 125900 KB Output is correct
21 Correct 54 ms 126064 KB Output is correct
22 Correct 60 ms 125948 KB Output is correct
23 Correct 55 ms 125932 KB Output is correct
24 Correct 439 ms 149116 KB Output is correct
25 Correct 494 ms 151560 KB Output is correct
26 Correct 443 ms 149168 KB Output is correct
27 Correct 504 ms 151504 KB Output is correct
28 Correct 573 ms 149740 KB Output is correct
29 Correct 451 ms 149072 KB Output is correct
30 Correct 983 ms 153556 KB Output is correct
31 Correct 135 ms 139172 KB Output is correct
32 Correct 402 ms 141384 KB Output is correct
33 Correct 626 ms 148692 KB Output is correct
34 Correct 973 ms 152208 KB Output is correct
35 Correct 1136 ms 152912 KB Output is correct
36 Correct 1149 ms 152636 KB Output is correct
37 Correct 552 ms 148080 KB Output is correct
38 Correct 666 ms 150468 KB Output is correct
39 Correct 494 ms 148236 KB Output is correct
40 Correct 459 ms 147948 KB Output is correct
41 Correct 49 ms 125564 KB Output is correct
42 Correct 998 ms 152324 KB Output is correct
43 Correct 580 ms 147348 KB Output is correct
44 Correct 893 ms 151028 KB Output is correct
45 Correct 984 ms 152568 KB Output is correct
46 Correct 2265 ms 228452 KB Output is correct
47 Correct 2679 ms 240744 KB Output is correct
48 Correct 2233 ms 229048 KB Output is correct
49 Correct 2233 ms 228420 KB Output is correct
50 Correct 5957 ms 250292 KB Output is correct
51 Correct 3244 ms 223376 KB Output is correct
52 Correct 4551 ms 240128 KB Output is correct
53 Correct 5653 ms 248940 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 150020 KB Output is correct
2 Correct 529 ms 150148 KB Output is correct
3 Correct 449 ms 149128 KB Output is correct
4 Correct 440 ms 146952 KB Output is correct
5 Correct 49 ms 125564 KB Output is correct
6 Correct 518 ms 149160 KB Output is correct
7 Correct 125 ms 136728 KB Output is correct
8 Correct 390 ms 141520 KB Output is correct
9 Correct 470 ms 148984 KB Output is correct
10 Correct 438 ms 149320 KB Output is correct
11 Correct 398 ms 149344 KB Output is correct
12 Correct 48 ms 125584 KB Output is correct
13 Correct 53 ms 125592 KB Output is correct
14 Correct 49 ms 125628 KB Output is correct
15 Correct 49 ms 125648 KB Output is correct
16 Correct 51 ms 125516 KB Output is correct
17 Correct 52 ms 125572 KB Output is correct
18 Correct 50 ms 125564 KB Output is correct
19 Correct 50 ms 125524 KB Output is correct
20 Correct 61 ms 125596 KB Output is correct
21 Correct 49 ms 125596 KB Output is correct
22 Correct 49 ms 125564 KB Output is correct
23 Correct 48 ms 125584 KB Output is correct
24 Correct 48 ms 125516 KB Output is correct
25 Correct 50 ms 125616 KB Output is correct
26 Correct 51 ms 125624 KB Output is correct
27 Correct 52 ms 125544 KB Output is correct
28 Correct 58 ms 125900 KB Output is correct
29 Correct 53 ms 126068 KB Output is correct
30 Correct 52 ms 126060 KB Output is correct
31 Correct 54 ms 125900 KB Output is correct
32 Correct 54 ms 126064 KB Output is correct
33 Correct 60 ms 125948 KB Output is correct
34 Correct 55 ms 125932 KB Output is correct
35 Correct 439 ms 149116 KB Output is correct
36 Correct 494 ms 151560 KB Output is correct
37 Correct 443 ms 149168 KB Output is correct
38 Correct 504 ms 151504 KB Output is correct
39 Correct 573 ms 149740 KB Output is correct
40 Correct 451 ms 149072 KB Output is correct
41 Correct 983 ms 153556 KB Output is correct
42 Correct 135 ms 139172 KB Output is correct
43 Correct 402 ms 141384 KB Output is correct
44 Correct 626 ms 148692 KB Output is correct
45 Correct 973 ms 152208 KB Output is correct
46 Correct 1136 ms 152912 KB Output is correct
47 Correct 1149 ms 152636 KB Output is correct
48 Correct 552 ms 148080 KB Output is correct
49 Correct 666 ms 150468 KB Output is correct
50 Correct 494 ms 148236 KB Output is correct
51 Correct 459 ms 147948 KB Output is correct
52 Correct 49 ms 125564 KB Output is correct
53 Correct 998 ms 152324 KB Output is correct
54 Correct 580 ms 147348 KB Output is correct
55 Correct 893 ms 151028 KB Output is correct
56 Correct 984 ms 152568 KB Output is correct
57 Correct 501 ms 146088 KB Output is correct
58 Correct 515 ms 148380 KB Output is correct
59 Correct 525 ms 146128 KB Output is correct
60 Correct 463 ms 146180 KB Output is correct
61 Correct 1112 ms 150716 KB Output is correct
62 Correct 51 ms 125636 KB Output is correct
63 Incorrect 997 ms 150500 KB Output isn't correct
64 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 150020 KB Output is correct
2 Correct 529 ms 150148 KB Output is correct
3 Correct 449 ms 149128 KB Output is correct
4 Correct 440 ms 146952 KB Output is correct
5 Correct 49 ms 125564 KB Output is correct
6 Correct 518 ms 149160 KB Output is correct
7 Correct 125 ms 136728 KB Output is correct
8 Correct 390 ms 141520 KB Output is correct
9 Correct 470 ms 148984 KB Output is correct
10 Correct 438 ms 149320 KB Output is correct
11 Correct 398 ms 149344 KB Output is correct
12 Correct 48 ms 125584 KB Output is correct
13 Correct 53 ms 125592 KB Output is correct
14 Correct 49 ms 125628 KB Output is correct
15 Correct 49 ms 125648 KB Output is correct
16 Correct 51 ms 125516 KB Output is correct
17 Correct 52 ms 125572 KB Output is correct
18 Correct 50 ms 125564 KB Output is correct
19 Correct 50 ms 125524 KB Output is correct
20 Correct 61 ms 125596 KB Output is correct
21 Correct 49 ms 125596 KB Output is correct
22 Correct 49 ms 125564 KB Output is correct
23 Correct 48 ms 125584 KB Output is correct
24 Correct 48 ms 125516 KB Output is correct
25 Correct 50 ms 125616 KB Output is correct
26 Correct 51 ms 125624 KB Output is correct
27 Correct 52 ms 125544 KB Output is correct
28 Correct 58 ms 125900 KB Output is correct
29 Correct 53 ms 126068 KB Output is correct
30 Correct 52 ms 126060 KB Output is correct
31 Correct 54 ms 125900 KB Output is correct
32 Correct 54 ms 126064 KB Output is correct
33 Correct 60 ms 125948 KB Output is correct
34 Correct 55 ms 125932 KB Output is correct
35 Correct 439 ms 149116 KB Output is correct
36 Correct 494 ms 151560 KB Output is correct
37 Correct 443 ms 149168 KB Output is correct
38 Correct 504 ms 151504 KB Output is correct
39 Correct 573 ms 149740 KB Output is correct
40 Correct 451 ms 149072 KB Output is correct
41 Correct 983 ms 153556 KB Output is correct
42 Correct 135 ms 139172 KB Output is correct
43 Correct 402 ms 141384 KB Output is correct
44 Correct 626 ms 148692 KB Output is correct
45 Correct 973 ms 152208 KB Output is correct
46 Correct 1136 ms 152912 KB Output is correct
47 Correct 1149 ms 152636 KB Output is correct
48 Correct 552 ms 148080 KB Output is correct
49 Correct 666 ms 150468 KB Output is correct
50 Correct 494 ms 148236 KB Output is correct
51 Correct 459 ms 147948 KB Output is correct
52 Correct 49 ms 125564 KB Output is correct
53 Correct 998 ms 152324 KB Output is correct
54 Correct 580 ms 147348 KB Output is correct
55 Correct 893 ms 151028 KB Output is correct
56 Correct 984 ms 152568 KB Output is correct
57 Correct 2265 ms 228452 KB Output is correct
58 Correct 2679 ms 240744 KB Output is correct
59 Correct 2233 ms 229048 KB Output is correct
60 Correct 2233 ms 228420 KB Output is correct
61 Correct 5957 ms 250292 KB Output is correct
62 Correct 3244 ms 223376 KB Output is correct
63 Correct 4551 ms 240128 KB Output is correct
64 Correct 5653 ms 248940 KB Output is correct
65 Correct 501 ms 146088 KB Output is correct
66 Correct 515 ms 148380 KB Output is correct
67 Correct 525 ms 146128 KB Output is correct
68 Correct 463 ms 146180 KB Output is correct
69 Correct 1112 ms 150716 KB Output is correct
70 Correct 51 ms 125636 KB Output is correct
71 Incorrect 997 ms 150500 KB Output isn't correct
72 Halted 0 ms 0 KB -