oj.uz

Submission #583581

# Submission time Handle Problem Language Result Execution time Memory
583581 2022-06-25T15:51:43 Z Johann Two Dishes (JOI19_dishes) C++14
5 / 100
 794 ms 51964 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;
    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) {
        size = 1;
        while (size < N) size *= 2;
        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 689 ms 49456 KB Output is correct
2 Correct 794 ms 49280 KB Output is correct
3 Correct 367 ms 46784 KB Output is correct
4 Correct 523 ms 49224 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 635 ms 48424 KB Output is correct
7 Correct 100 ms 42080 KB Output is correct
8 Correct 92 ms 28632 KB Output is correct
9 Correct 347 ms 46752 KB Output is correct
10 Correct 663 ms 51964 KB Output is correct
11 Correct 299 ms 46748 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 14 ms 23748 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 14 ms 23808 KB Output is correct
7 Correct 15 ms 23800 KB Output is correct
8 Correct 14 ms 23820 KB Output is correct
9 Correct 16 ms 23764 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 14 ms 23764 KB Output is correct
12 Correct 14 ms 23784 KB Output is correct
13 Incorrect 14 ms 23764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 14 ms 23748 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 14 ms 23808 KB Output is correct
7 Correct 15 ms 23800 KB Output is correct
8 Correct 14 ms 23820 KB Output is correct
9 Correct 16 ms 23764 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 14 ms 23764 KB Output is correct
12 Correct 14 ms 23784 KB Output is correct
13 Incorrect 14 ms 23764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 14 ms 23748 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 14 ms 23808 KB Output is correct
7 Correct 15 ms 23800 KB Output is correct
8 Correct 14 ms 23820 KB Output is correct
9 Correct 16 ms 23764 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 14 ms 23764 KB Output is correct
12 Correct 14 ms 23784 KB Output is correct
13 Incorrect 14 ms 23764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 14 ms 23748 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 14 ms 23808 KB Output is correct
7 Correct 15 ms 23800 KB Output is correct
8 Correct 14 ms 23820 KB Output is correct
9 Correct 16 ms 23764 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 14 ms 23764 KB Output is correct
12 Correct 14 ms 23784 KB Output is correct
13 Incorrect 14 ms 23764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 14 ms 23748 KB Output is correct
5 Correct 14 ms 23764 KB Output is correct
6 Correct 14 ms 23808 KB Output is correct
7 Correct 15 ms 23800 KB Output is correct
8 Correct 14 ms 23820 KB Output is correct
9 Correct 16 ms 23764 KB Output is correct
10 Correct 13 ms 23764 KB Output is correct
11 Correct 14 ms 23764 KB Output is correct
12 Correct 14 ms 23784 KB Output is correct
13 Incorrect 14 ms 23764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 49456 KB Output is correct
2 Correct 794 ms 49280 KB Output is correct
3 Correct 367 ms 46784 KB Output is correct
4 Correct 523 ms 49224 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 635 ms 48424 KB Output is correct
7 Correct 100 ms 42080 KB Output is correct
8 Correct 92 ms 28632 KB Output is correct
9 Correct 347 ms 46752 KB Output is correct
10 Correct 663 ms 51964 KB Output is correct
11 Correct 299 ms 46748 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 13 ms 23764 KB Output is correct
15 Correct 14 ms 23748 KB Output is correct
16 Correct 14 ms 23764 KB Output is correct
17 Correct 14 ms 23808 KB Output is correct
18 Correct 15 ms 23800 KB Output is correct
19 Correct 14 ms 23820 KB Output is correct
20 Correct 16 ms 23764 KB Output is correct
21 Correct 13 ms 23764 KB Output is correct
22 Correct 14 ms 23764 KB Output is correct
23 Correct 14 ms 23784 KB Output is correct
24 Incorrect 14 ms 23764 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 49456 KB Output is correct
2 Correct 794 ms 49280 KB Output is correct
3 Correct 367 ms 46784 KB Output is correct
4 Correct 523 ms 49224 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 635 ms 48424 KB Output is correct
7 Correct 100 ms 42080 KB Output is correct
8 Correct 92 ms 28632 KB Output is correct
9 Correct 347 ms 46752 KB Output is correct
10 Correct 663 ms 51964 KB Output is correct
11 Correct 299 ms 46748 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 13 ms 23764 KB Output is correct
15 Correct 14 ms 23748 KB Output is correct
16 Correct 14 ms 23764 KB Output is correct
17 Correct 14 ms 23808 KB Output is correct
18 Correct 15 ms 23800 KB Output is correct
19 Correct 14 ms 23820 KB Output is correct
20 Correct 16 ms 23764 KB Output is correct
21 Correct 13 ms 23764 KB Output is correct
22 Correct 14 ms 23764 KB Output is correct
23 Correct 14 ms 23784 KB Output is correct
24 Incorrect 14 ms 23764 KB Output isn't correct
25 Halted 0 ms 0 KB -