oj.uz

Submission #974543

# Submission time Handle Problem Language Result Execution time Memory
974543 2024-05-03T12:39:48 Z DAleksa Two Dishes (JOI19_dishes) C++17
74 / 100
 4160 ms 292436 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

struct node {
    long long mx;
    long long add;
    long long set;
    bool both;
    node() {
        mx = 0;
        add = 0;
        set = 0;
        both = false;
    }
};

struct pt {
    int y;
    long long val;
};

const int N = 1e6 + 10;
const long long inf = 4e16;
int n, m;
long long a[N], p[N], b[N], q[N];
long long s[N], t[N];
int x[N], y[N];
vector<pt> all[N];
node st[4 * N];

void propagate(int index) {
    if(2 * index + 1 < 4 * N) {
        if(st[index].both) {
            long long val = st[index].set + st[index].add;
            st[2 * index].mx = val;
            st[2 * index].set = val;
            st[2 * index].add = 0;
            st[2 * index].both = true;
            st[2 * index + 1].mx = val;
            st[2 * index + 1].set = val;
            st[2 * index + 1].add = 0;
            st[2 * index + 1].both = true;
            st[index].add = 0;
            st[index].set = 0;
            st[index].both = false;
        } else {
            st[2 * index].mx += st[index].add;
            st[2 * index].add += st[index].add;
            st[2 * index + 1].mx += st[index].add;
            st[2 * index + 1].add += st[index].add;
            st[index].add = 0;
        }
    }
}

void update(int index, int l, int r, int L, int R, long long val) {
    if(l > r || r < L || R < l) return;
    if(L <= l && r <= R) {
        st[index].mx += val;
        st[index].add += val;
        return;
    }
    propagate(index);
    int mid = (l + r) / 2;
    update(2 * index, l, mid, L, R, val);
    update(2 * index + 1, mid + 1, r, L, R, val);
    st[index].mx = max(st[2 * index].mx, st[2 * index + 1].mx);
}

void modify(int index, int l, int r, int L, int R, long long val) {
    if(l > r || r < L || R < l) return;
    if(L <= l && r <= R) {
        st[index].mx = val;
        st[index].set = val;
        st[index].both = true;
        st[index].add = 0;
        return;
    }
    propagate(index);
    int mid = (l + r) / 2;
    modify(2 * index, l, mid, L, R, val);
    modify(2 * index + 1, mid + 1, r, L, R, val);
    st[index].mx = max(st[2 * index].mx, st[2 * index + 1].mx);
}

long long get(int index, int l, int r, int x) {
    if(l > r || r < x || x < l) return -inf;
    if(l == r) return st[index].mx;
    propagate(index);
    int mid = (l + r) / 2;
    return max(get(2 * index, l, mid, x), get(2 * index + 1, mid + 1, r, x));
}

int walk(int index, int l, int r, int x, long long val) {
    if(l > r || r < x) return r;
    if(l == r) {
        if(st[index].mx >= val) return l - 1;
        return l;
    }
    if(st[index].mx < val) return r;
    propagate(index);
    int mid = (l + r) / 2;
    int L = walk(2 * index, l, mid, x, val);
    if(L != mid) return L;
    return walk(2 * index + 1, mid + 1, r, x, val);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i] >> s[i] >> p[i];
    for(int i = 1; i <= m; i++) cin >> b[i] >> t[i] >> q[i];
    a[0] = b[0] = 0;
    for(int i = 2; i <= n; i++) a[i] += a[i - 1];
    for(int i = 2; i <= m; i++) b[i] += b[i - 1];
    for(int i = 1; i <= n; i++) {
        if(a[i] > s[i]) {
            x[i] = -1;
            continue;
        }
        int l = 0, r = m;
        int ans = l;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(a[i] + b[mid] <= s[i]) {
                ans = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        x[i] = ans;
    }
    for(int i = 1; i <= m; i++) {
        if(b[i] > t[i]) {
            y[i] = -1;
            continue;
        }
        int l = 0, r = n;
        int ans = l;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(a[mid] + b[i] <= t[i]) {
                ans = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        y[i] = ans;
    }
    long long add = 0;
    for(int i = 1; i <= n; i++) {
        if(x[i] == -1) continue;
        add += p[i];
        if(x[i] < m) all[x[i] + 1].push_back({i - 1, -p[i]});
    }
    for(int i = 1; i <= m; i++) {
        if(y[i] == -1) continue;
        all[i].push_back({y[i], q[i]});
    }
    for(int i = 1; i <= m; i++) {
        sort(all[i].begin(), all[i].end(), [&](pt p1, pt p2) {
            return p1.y > p2.y;
        });
    }
    // modify(1, 0, n, 1, n, 39);
    // for(int i = 0; i <= n; i++) cout << get(1, 0, n, i) << " ";
    // return 0;
    // cout << "POINTS:\n";
    // for(int i = 0; i <= m; i++) {
    //     for(pt p : all[i]) cout << i << " " << p.y << " " << p.val << "\n";
    // }
    for(int i = 0; i <= m; i++) {
        // cout << "#" << i << ":\nPOINTS:\n";
        for(pt p : all[i]) {
            int y = p.y;
            long long val = p.val;
            // cout << y << " " << val << "\n";
            update(1, 0, n, 0, y, val);
            long long mx = get(1, 0, n, y);
            int nxt = walk(1, 0, n, y + 1, mx);
            // cout << mx << " " << nxt << "\n";
            modify(1, 0, n, y, nxt, mx);
            // cout << "TREE:\n";
            // for(int j = 0; j <= n; j++) cout << get(1, 0, n, j) << " ";
            // cout << "\n";
        }
        // cout << "\n";
    }
    // for(int i = 1; i <= m; i++) {
    //     for(pt p : all[i]) cout << i << " " << p.y << " " << p.val << "\n";
    // }
    // for(int i = 1; i <= n; i++) cout << x[i] << " ";
    // cout << "\n";
    // for(int i = 1; i <= m; i++) cout << y[i] << " ";
    // cout << "\n";
    // cout << add << "\n";
    cout << get(1, 0, n, n) + add;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 178508 KB Output is correct
2 Correct 398 ms 178748 KB Output is correct
3 Correct 206 ms 175360 KB Output is correct
4 Correct 306 ms 174932 KB Output is correct
5 Correct 37 ms 150364 KB Output is correct
6 Correct 403 ms 177652 KB Output is correct
7 Correct 97 ms 165184 KB Output is correct
8 Correct 90 ms 160764 KB Output is correct
9 Correct 217 ms 175760 KB Output is correct
10 Correct 390 ms 175580 KB Output is correct
11 Correct 195 ms 172364 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 150452 KB Output is correct
2 Correct 34 ms 150364 KB Output is correct
3 Correct 35 ms 150364 KB Output is correct
4 Correct 35 ms 150272 KB Output is correct
5 Correct 36 ms 150356 KB Output is correct
6 Correct 34 ms 150224 KB Output is correct
7 Correct 34 ms 150364 KB Output is correct
8 Correct 37 ms 150336 KB Output is correct
9 Correct 36 ms 150296 KB Output is correct
10 Correct 34 ms 150360 KB Output is correct
11 Correct 34 ms 150352 KB Output is correct
12 Correct 34 ms 150352 KB Output is correct
13 Correct 35 ms 150352 KB Output is correct
14 Correct 35 ms 150372 KB Output is correct
15 Correct 34 ms 150456 KB Output is correct
16 Correct 36 ms 150364 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 150452 KB Output is correct
2 Correct 34 ms 150364 KB Output is correct
3 Correct 35 ms 150364 KB Output is correct
4 Correct 35 ms 150272 KB Output is correct
5 Correct 36 ms 150356 KB Output is correct
6 Correct 34 ms 150224 KB Output is correct
7 Correct 34 ms 150364 KB Output is correct
8 Correct 37 ms 150336 KB Output is correct
9 Correct 36 ms 150296 KB Output is correct
10 Correct 34 ms 150360 KB Output is correct
11 Correct 34 ms 150352 KB Output is correct
12 Correct 34 ms 150352 KB Output is correct
13 Correct 35 ms 150352 KB Output is correct
14 Correct 35 ms 150372 KB Output is correct
15 Correct 34 ms 150456 KB Output is correct
16 Correct 36 ms 150364 KB Output is correct
17 Correct 36 ms 150620 KB Output is correct
18 Correct 39 ms 150624 KB Output is correct
19 Correct 40 ms 150616 KB Output is correct
20 Correct 41 ms 150644 KB Output is correct
21 Correct 41 ms 150864 KB Output is correct
22 Correct 41 ms 150608 KB Output is correct
23 Correct 41 ms 150608 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 150452 KB Output is correct
2 Correct 34 ms 150364 KB Output is correct
3 Correct 35 ms 150364 KB Output is correct
4 Correct 35 ms 150272 KB Output is correct
5 Correct 36 ms 150356 KB Output is correct
6 Correct 34 ms 150224 KB Output is correct
7 Correct 34 ms 150364 KB Output is correct
8 Correct 37 ms 150336 KB Output is correct
9 Correct 36 ms 150296 KB Output is correct
10 Correct 34 ms 150360 KB Output is correct
11 Correct 34 ms 150352 KB Output is correct
12 Correct 34 ms 150352 KB Output is correct
13 Correct 35 ms 150352 KB Output is correct
14 Correct 35 ms 150372 KB Output is correct
15 Correct 34 ms 150456 KB Output is correct
16 Correct 36 ms 150364 KB Output is correct
17 Correct 36 ms 150620 KB Output is correct
18 Correct 39 ms 150624 KB Output is correct
19 Correct 40 ms 150616 KB Output is correct
20 Correct 41 ms 150644 KB Output is correct
21 Correct 41 ms 150864 KB Output is correct
22 Correct 41 ms 150608 KB Output is correct
23 Correct 41 ms 150608 KB Output is correct
24 Correct 300 ms 173764 KB Output is correct
25 Correct 258 ms 173892 KB Output is correct
26 Correct 396 ms 179284 KB Output is correct
27 Correct 255 ms 173648 KB Output is correct
28 Correct 301 ms 174556 KB Output is correct
29 Correct 232 ms 174408 KB Output is correct
30 Correct 807 ms 177500 KB Output is correct
31 Correct 91 ms 164972 KB Output is correct
32 Correct 160 ms 165776 KB Output is correct
33 Correct 453 ms 172888 KB Output is correct
34 Correct 591 ms 176464 KB Output is correct
35 Correct 605 ms 174372 KB Output is correct
36 Correct 656 ms 174308 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 150452 KB Output is correct
2 Correct 34 ms 150364 KB Output is correct
3 Correct 35 ms 150364 KB Output is correct
4 Correct 35 ms 150272 KB Output is correct
5 Correct 36 ms 150356 KB Output is correct
6 Correct 34 ms 150224 KB Output is correct
7 Correct 34 ms 150364 KB Output is correct
8 Correct 37 ms 150336 KB Output is correct
9 Correct 36 ms 150296 KB Output is correct
10 Correct 34 ms 150360 KB Output is correct
11 Correct 34 ms 150352 KB Output is correct
12 Correct 34 ms 150352 KB Output is correct
13 Correct 35 ms 150352 KB Output is correct
14 Correct 35 ms 150372 KB Output is correct
15 Correct 34 ms 150456 KB Output is correct
16 Correct 36 ms 150364 KB Output is correct
17 Correct 36 ms 150620 KB Output is correct
18 Correct 39 ms 150624 KB Output is correct
19 Correct 40 ms 150616 KB Output is correct
20 Correct 41 ms 150644 KB Output is correct
21 Correct 41 ms 150864 KB Output is correct
22 Correct 41 ms 150608 KB Output is correct
23 Correct 41 ms 150608 KB Output is correct
24 Correct 300 ms 173764 KB Output is correct
25 Correct 258 ms 173892 KB Output is correct
26 Correct 396 ms 179284 KB Output is correct
27 Correct 255 ms 173648 KB Output is correct
28 Correct 301 ms 174556 KB Output is correct
29 Correct 232 ms 174408 KB Output is correct
30 Correct 807 ms 177500 KB Output is correct
31 Correct 91 ms 164972 KB Output is correct
32 Correct 160 ms 165776 KB Output is correct
33 Correct 453 ms 172888 KB Output is correct
34 Correct 591 ms 176464 KB Output is correct
35 Correct 605 ms 174372 KB Output is correct
36 Correct 656 ms 174308 KB Output is correct
37 Correct 317 ms 178128 KB Output is correct
38 Correct 269 ms 175188 KB Output is correct
39 Correct 466 ms 179172 KB Output is correct
40 Correct 400 ms 177376 KB Output is correct
41 Correct 39 ms 150268 KB Output is correct
42 Correct 668 ms 181904 KB Output is correct
43 Correct 405 ms 187836 KB Output is correct
44 Correct 545 ms 191664 KB Output is correct
45 Correct 639 ms 189524 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 150452 KB Output is correct
2 Correct 34 ms 150364 KB Output is correct
3 Correct 35 ms 150364 KB Output is correct
4 Correct 35 ms 150272 KB Output is correct
5 Correct 36 ms 150356 KB Output is correct
6 Correct 34 ms 150224 KB Output is correct
7 Correct 34 ms 150364 KB Output is correct
8 Correct 37 ms 150336 KB Output is correct
9 Correct 36 ms 150296 KB Output is correct
10 Correct 34 ms 150360 KB Output is correct
11 Correct 34 ms 150352 KB Output is correct
12 Correct 34 ms 150352 KB Output is correct
13 Correct 35 ms 150352 KB Output is correct
14 Correct 35 ms 150372 KB Output is correct
15 Correct 34 ms 150456 KB Output is correct
16 Correct 36 ms 150364 KB Output is correct
17 Correct 36 ms 150620 KB Output is correct
18 Correct 39 ms 150624 KB Output is correct
19 Correct 40 ms 150616 KB Output is correct
20 Correct 41 ms 150644 KB Output is correct
21 Correct 41 ms 150864 KB Output is correct
22 Correct 41 ms 150608 KB Output is correct
23 Correct 41 ms 150608 KB Output is correct
24 Correct 300 ms 173764 KB Output is correct
25 Correct 258 ms 173892 KB Output is correct
26 Correct 396 ms 179284 KB Output is correct
27 Correct 255 ms 173648 KB Output is correct
28 Correct 301 ms 174556 KB Output is correct
29 Correct 232 ms 174408 KB Output is correct
30 Correct 807 ms 177500 KB Output is correct
31 Correct 91 ms 164972 KB Output is correct
32 Correct 160 ms 165776 KB Output is correct
33 Correct 453 ms 172888 KB Output is correct
34 Correct 591 ms 176464 KB Output is correct
35 Correct 605 ms 174372 KB Output is correct
36 Correct 656 ms 174308 KB Output is correct
37 Correct 317 ms 178128 KB Output is correct
38 Correct 269 ms 175188 KB Output is correct
39 Correct 466 ms 179172 KB Output is correct
40 Correct 400 ms 177376 KB Output is correct
41 Correct 39 ms 150268 KB Output is correct
42 Correct 668 ms 181904 KB Output is correct
43 Correct 405 ms 187836 KB Output is correct
44 Correct 545 ms 191664 KB Output is correct
45 Correct 639 ms 189524 KB Output is correct
46 Correct 1587 ms 292436 KB Output is correct
47 Correct 1309 ms 278680 KB Output is correct
48 Correct 2365 ms 280336 KB Output is correct
49 Correct 2025 ms 258968 KB Output is correct
50 Correct 4160 ms 261940 KB Output is correct
51 Correct 2183 ms 237812 KB Output is correct
52 Correct 2707 ms 253592 KB Output is correct
53 Correct 3772 ms 260568 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 178508 KB Output is correct
2 Correct 398 ms 178748 KB Output is correct
3 Correct 206 ms 175360 KB Output is correct
4 Correct 306 ms 174932 KB Output is correct
5 Correct 37 ms 150364 KB Output is correct
6 Correct 403 ms 177652 KB Output is correct
7 Correct 97 ms 165184 KB Output is correct
8 Correct 90 ms 160764 KB Output is correct
9 Correct 217 ms 175760 KB Output is correct
10 Correct 390 ms 175580 KB Output is correct
11 Correct 195 ms 172364 KB Output is correct
12 Correct 34 ms 150452 KB Output is correct
13 Correct 34 ms 150364 KB Output is correct
14 Correct 35 ms 150364 KB Output is correct
15 Correct 35 ms 150272 KB Output is correct
16 Correct 36 ms 150356 KB Output is correct
17 Correct 34 ms 150224 KB Output is correct
18 Correct 34 ms 150364 KB Output is correct
19 Correct 37 ms 150336 KB Output is correct
20 Correct 36 ms 150296 KB Output is correct
21 Correct 34 ms 150360 KB Output is correct
22 Correct 34 ms 150352 KB Output is correct
23 Correct 34 ms 150352 KB Output is correct
24 Correct 35 ms 150352 KB Output is correct
25 Correct 35 ms 150372 KB Output is correct
26 Correct 34 ms 150456 KB Output is correct
27 Correct 36 ms 150364 KB Output is correct
28 Correct 36 ms 150620 KB Output is correct
29 Correct 39 ms 150624 KB Output is correct
30 Correct 40 ms 150616 KB Output is correct
31 Correct 41 ms 150644 KB Output is correct
32 Correct 41 ms 150864 KB Output is correct
33 Correct 41 ms 150608 KB Output is correct
34 Correct 41 ms 150608 KB Output is correct
35 Correct 300 ms 173764 KB Output is correct
36 Correct 258 ms 173892 KB Output is correct
37 Correct 396 ms 179284 KB Output is correct
38 Correct 255 ms 173648 KB Output is correct
39 Correct 301 ms 174556 KB Output is correct
40 Correct 232 ms 174408 KB Output is correct
41 Correct 807 ms 177500 KB Output is correct
42 Correct 91 ms 164972 KB Output is correct
43 Correct 160 ms 165776 KB Output is correct
44 Correct 453 ms 172888 KB Output is correct
45 Correct 591 ms 176464 KB Output is correct
46 Correct 605 ms 174372 KB Output is correct
47 Correct 656 ms 174308 KB Output is correct
48 Correct 317 ms 178128 KB Output is correct
49 Correct 269 ms 175188 KB Output is correct
50 Correct 466 ms 179172 KB Output is correct
51 Correct 400 ms 177376 KB Output is correct
52 Correct 39 ms 150268 KB Output is correct
53 Correct 668 ms 181904 KB Output is correct
54 Correct 405 ms 187836 KB Output is correct
55 Correct 545 ms 191664 KB Output is correct
56 Correct 639 ms 189524 KB Output is correct
57 Correct 336 ms 183892 KB Output is correct
58 Correct 271 ms 181292 KB Output is correct
59 Incorrect 392 ms 184404 KB Output isn't correct
60 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 178508 KB Output is correct
2 Correct 398 ms 178748 KB Output is correct
3 Correct 206 ms 175360 KB Output is correct
4 Correct 306 ms 174932 KB Output is correct
5 Correct 37 ms 150364 KB Output is correct
6 Correct 403 ms 177652 KB Output is correct
7 Correct 97 ms 165184 KB Output is correct
8 Correct 90 ms 160764 KB Output is correct
9 Correct 217 ms 175760 KB Output is correct
10 Correct 390 ms 175580 KB Output is correct
11 Correct 195 ms 172364 KB Output is correct
12 Correct 34 ms 150452 KB Output is correct
13 Correct 34 ms 150364 KB Output is correct
14 Correct 35 ms 150364 KB Output is correct
15 Correct 35 ms 150272 KB Output is correct
16 Correct 36 ms 150356 KB Output is correct
17 Correct 34 ms 150224 KB Output is correct
18 Correct 34 ms 150364 KB Output is correct
19 Correct 37 ms 150336 KB Output is correct
20 Correct 36 ms 150296 KB Output is correct
21 Correct 34 ms 150360 KB Output is correct
22 Correct 34 ms 150352 KB Output is correct
23 Correct 34 ms 150352 KB Output is correct
24 Correct 35 ms 150352 KB Output is correct
25 Correct 35 ms 150372 KB Output is correct
26 Correct 34 ms 150456 KB Output is correct
27 Correct 36 ms 150364 KB Output is correct
28 Correct 36 ms 150620 KB Output is correct
29 Correct 39 ms 150624 KB Output is correct
30 Correct 40 ms 150616 KB Output is correct
31 Correct 41 ms 150644 KB Output is correct
32 Correct 41 ms 150864 KB Output is correct
33 Correct 41 ms 150608 KB Output is correct
34 Correct 41 ms 150608 KB Output is correct
35 Correct 300 ms 173764 KB Output is correct
36 Correct 258 ms 173892 KB Output is correct
37 Correct 396 ms 179284 KB Output is correct
38 Correct 255 ms 173648 KB Output is correct
39 Correct 301 ms 174556 KB Output is correct
40 Correct 232 ms 174408 KB Output is correct
41 Correct 807 ms 177500 KB Output is correct
42 Correct 91 ms 164972 KB Output is correct
43 Correct 160 ms 165776 KB Output is correct
44 Correct 453 ms 172888 KB Output is correct
45 Correct 591 ms 176464 KB Output is correct
46 Correct 605 ms 174372 KB Output is correct
47 Correct 656 ms 174308 KB Output is correct
48 Correct 317 ms 178128 KB Output is correct
49 Correct 269 ms 175188 KB Output is correct
50 Correct 466 ms 179172 KB Output is correct
51 Correct 400 ms 177376 KB Output is correct
52 Correct 39 ms 150268 KB Output is correct
53 Correct 668 ms 181904 KB Output is correct
54 Correct 405 ms 187836 KB Output is correct
55 Correct 545 ms 191664 KB Output is correct
56 Correct 639 ms 189524 KB Output is correct
57 Correct 1587 ms 292436 KB Output is correct
58 Correct 1309 ms 278680 KB Output is correct
59 Correct 2365 ms 280336 KB Output is correct
60 Correct 2025 ms 258968 KB Output is correct
61 Correct 4160 ms 261940 KB Output is correct
62 Correct 2183 ms 237812 KB Output is correct
63 Correct 2707 ms 253592 KB Output is correct
64 Correct 3772 ms 260568 KB Output is correct
65 Correct 336 ms 183892 KB Output is correct
66 Correct 271 ms 181292 KB Output is correct
67 Incorrect 392 ms 184404 KB Output isn't correct
68 Halted 0 ms 0 KB -