oj.uz

Submission #583582

# Submission time Handle Problem Language Result Execution time Memory
583582 2022-06-25T15:53:05 Z Johann Two Dishes (JOI19_dishes) C++14
5 / 100
 734 ms 88764 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll,ll>
#define vi vector<ll>
#define vpii vector<pii>
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

const ll inf = 1LL << 60;

struct operation {
    ll addopt=0;
    ll maxopt=-inf;
};
struct segtree {
    int size = 1 << 20;
    vector<ll> arr;
    vector<operation> opt;
    ll combine(ll ld, ll rd) {
        return max(ld, rd);
    }
    ll calculate(operation o, ll d) {
        return max(o.maxopt, d + o.addopt);
    }
    operation merge(operation ot, operation ob) {
        return { ot.addopt + ob.addopt, max(ot.maxopt, ob.maxopt) };
    }
    segtree(int N) {
        arr.assign(2*size, 0);
        opt.assign(2*size, operation());
    }
    void apply(int x, operation & o) {
        arr[x] = calculate(o, arr[x]);
        if (x < size)
            opt[x] = merge(opt[x], o);
    }
    void push(int x) {
        apply(2 * x, opt[x]);
        apply(2*x+1, opt[x]);
        opt[x] = operation();
    }
    ll query(int l, int r, int x, int lx, int rx) {
        if (l <= lx && rx <= r) { return arr[x]; }
        if (rx <= l || r <= lx) { return -inf; }
        push(x);
        int m = ( lx + rx ) / 2;
        ll lv = query(l, r, 2 * x, lx, m);
        ll rv = query(l, r, 2*x+1, m, rx);
        return combine(lv, rv);
    }
    void apply(int l, int r, operation o, int x, int lx, int rx) { // add or max
        if (l <= lx && rx <= r) { apply(x, o); return; }
        if (rx <= l || r <= lx) { return; }
        push(x);
        int m = ( lx + rx ) / 2;
        apply(l, r, o, 2 * x, lx, m);
        apply(l, r, o, 2*x+1, m, rx);
        arr[x] = combine(arr[2 * x], arr[2*x+1]);
    }
    void apply(int l, int r, operation o) {
        apply(l, r, o, 1, 0, size);
    }
    ll query(int l, int r){
        return query(l, r, 1, 0, size);
    }
};

const int MAXN = 1000100;
ll N[2];
ll A[2][MAXN],T[2][MAXN],P[2][MAXN];
vector<int> rem[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N[0] >> N[1];
    for (int j = 0; j < 2; ++j) {
        for (int i = 0; i < N[j]; ++i) {
            cin >> A[j][i] >> T[j][i] >> P[j][i];
            if (i > 0) A[j][i] += A[j][i-1]; // A ist eine Präfixsumme
            T[j][i] -= A[j][i]; // Wie viel darf ich vom anderen machen, ich noch Punkte bekomme?
        }
    }

    // Segmentbaum auf N[1] aufgebaut
    segtree seg = segtree(N[1]+1);
    // Index shift bei j um 1!
    // init 0th layer:
    ll p1 = 0;
    for (int j = 0; j < N[1]; ++j) {
        if (T[1][j] >= 0) {
            p1 += P[1][j];
            int k = upper_bound(A[0], A[0] + N[0], T[1][j]) - A[0];
            rem[k].push_back(j);
        }
    }
    seg.apply(0, N[1]+1, { p1, -inf });
    // ernst
    for (int i = 0; i < N[0]; ++i) {
        vi cuts;
        for (int j : rem[i]) {
            seg.apply(0, j+1, { - P[1][j], -inf });
            cuts.push_back(j+1);
            // for (int i = 0; i <= N[1]; ++i) cout << seg.query(i, i+1) << " "; cout << endl;
        }
        if (T[0][i] >= 0) {
            ll j = upper_bound(A[1], A[1] + N[1], T[0][i]) - A[1];
            seg.apply(0, j+1, { P[0][i], -inf });
            cuts.push_back(j+1);
            // for (int i = 0; i <= N[1]; ++i) cout << seg.query(i, i+1) << " "; cout << endl;
        }
        for (int x : cuts) {
            ll v = seg.query(0, x);
            seg.apply(x, N[1]+1, { 0, v });
            // for (int i = 0; i <= N[1]; ++i) cout << seg.query(i, i+1) << " "; cout << endl;
        }
    }
    cout << seg.query(0, N[1]+1) << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 86260 KB Output is correct
2 Correct 705 ms 85972 KB Output is correct
3 Correct 380 ms 83588 KB Output is correct
4 Correct 592 ms 86136 KB Output is correct
5 Correct 34 ms 73032 KB Output is correct
6 Correct 645 ms 85384 KB Output is correct
7 Correct 110 ms 78980 KB Output is correct
8 Correct 310 ms 77716 KB Output is correct
9 Correct 379 ms 83648 KB Output is correct
10 Correct 734 ms 88764 KB Output is correct
11 Correct 338 ms 83584 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 73004 KB Output is correct
2 Correct 32 ms 72996 KB Output is correct
3 Correct 38 ms 73008 KB Output is correct
4 Correct 33 ms 73048 KB Output is correct
5 Correct 37 ms 73084 KB Output is correct
6 Correct 34 ms 73032 KB Output is correct
7 Correct 31 ms 73068 KB Output is correct
8 Correct 34 ms 73056 KB Output is correct
9 Correct 33 ms 73072 KB Output is correct
10 Correct 34 ms 73068 KB Output is correct
11 Correct 32 ms 73028 KB Output is correct
12 Correct 31 ms 73048 KB Output is correct
13 Incorrect 33 ms 73048 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 73004 KB Output is correct
2 Correct 32 ms 72996 KB Output is correct
3 Correct 38 ms 73008 KB Output is correct
4 Correct 33 ms 73048 KB Output is correct
5 Correct 37 ms 73084 KB Output is correct
6 Correct 34 ms 73032 KB Output is correct
7 Correct 31 ms 73068 KB Output is correct
8 Correct 34 ms 73056 KB Output is correct
9 Correct 33 ms 73072 KB Output is correct
10 Correct 34 ms 73068 KB Output is correct
11 Correct 32 ms 73028 KB Output is correct
12 Correct 31 ms 73048 KB Output is correct
13 Incorrect 33 ms 73048 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 73004 KB Output is correct
2 Correct 32 ms 72996 KB Output is correct
3 Correct 38 ms 73008 KB Output is correct
4 Correct 33 ms 73048 KB Output is correct
5 Correct 37 ms 73084 KB Output is correct
6 Correct 34 ms 73032 KB Output is correct
7 Correct 31 ms 73068 KB Output is correct
8 Correct 34 ms 73056 KB Output is correct
9 Correct 33 ms 73072 KB Output is correct
10 Correct 34 ms 73068 KB Output is correct
11 Correct 32 ms 73028 KB Output is correct
12 Correct 31 ms 73048 KB Output is correct
13 Incorrect 33 ms 73048 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 73004 KB Output is correct
2 Correct 32 ms 72996 KB Output is correct
3 Correct 38 ms 73008 KB Output is correct
4 Correct 33 ms 73048 KB Output is correct
5 Correct 37 ms 73084 KB Output is correct
6 Correct 34 ms 73032 KB Output is correct
7 Correct 31 ms 73068 KB Output is correct
8 Correct 34 ms 73056 KB Output is correct
9 Correct 33 ms 73072 KB Output is correct
10 Correct 34 ms 73068 KB Output is correct
11 Correct 32 ms 73028 KB Output is correct
12 Correct 31 ms 73048 KB Output is correct
13 Incorrect 33 ms 73048 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 73004 KB Output is correct
2 Correct 32 ms 72996 KB Output is correct
3 Correct 38 ms 73008 KB Output is correct
4 Correct 33 ms 73048 KB Output is correct
5 Correct 37 ms 73084 KB Output is correct
6 Correct 34 ms 73032 KB Output is correct
7 Correct 31 ms 73068 KB Output is correct
8 Correct 34 ms 73056 KB Output is correct
9 Correct 33 ms 73072 KB Output is correct
10 Correct 34 ms 73068 KB Output is correct
11 Correct 32 ms 73028 KB Output is correct
12 Correct 31 ms 73048 KB Output is correct
13 Incorrect 33 ms 73048 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 86260 KB Output is correct
2 Correct 705 ms 85972 KB Output is correct
3 Correct 380 ms 83588 KB Output is correct
4 Correct 592 ms 86136 KB Output is correct
5 Correct 34 ms 73032 KB Output is correct
6 Correct 645 ms 85384 KB Output is correct
7 Correct 110 ms 78980 KB Output is correct
8 Correct 310 ms 77716 KB Output is correct
9 Correct 379 ms 83648 KB Output is correct
10 Correct 734 ms 88764 KB Output is correct
11 Correct 338 ms 83584 KB Output is correct
12 Correct 37 ms 73004 KB Output is correct
13 Correct 32 ms 72996 KB Output is correct
14 Correct 38 ms 73008 KB Output is correct
15 Correct 33 ms 73048 KB Output is correct
16 Correct 37 ms 73084 KB Output is correct
17 Correct 34 ms 73032 KB Output is correct
18 Correct 31 ms 73068 KB Output is correct
19 Correct 34 ms 73056 KB Output is correct
20 Correct 33 ms 73072 KB Output is correct
21 Correct 34 ms 73068 KB Output is correct
22 Correct 32 ms 73028 KB Output is correct
23 Correct 31 ms 73048 KB Output is correct
24 Incorrect 33 ms 73048 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 86260 KB Output is correct
2 Correct 705 ms 85972 KB Output is correct
3 Correct 380 ms 83588 KB Output is correct
4 Correct 592 ms 86136 KB Output is correct
5 Correct 34 ms 73032 KB Output is correct
6 Correct 645 ms 85384 KB Output is correct
7 Correct 110 ms 78980 KB Output is correct
8 Correct 310 ms 77716 KB Output is correct
9 Correct 379 ms 83648 KB Output is correct
10 Correct 734 ms 88764 KB Output is correct
11 Correct 338 ms 83584 KB Output is correct
12 Correct 37 ms 73004 KB Output is correct
13 Correct 32 ms 72996 KB Output is correct
14 Correct 38 ms 73008 KB Output is correct
15 Correct 33 ms 73048 KB Output is correct
16 Correct 37 ms 73084 KB Output is correct
17 Correct 34 ms 73032 KB Output is correct
18 Correct 31 ms 73068 KB Output is correct
19 Correct 34 ms 73056 KB Output is correct
20 Correct 33 ms 73072 KB Output is correct
21 Correct 34 ms 73068 KB Output is correct
22 Correct 32 ms 73028 KB Output is correct
23 Correct 31 ms 73048 KB Output is correct
24 Incorrect 33 ms 73048 KB Output isn't correct
25 Halted 0 ms 0 KB -