oj.uz

Submission #366910

# Submission time Handle Problem Language Result Execution time Memory
366910 2021-02-15T17:50:28 Z valerikk Two Dishes (JOI19_dishes) C++17
100 / 100
 4681 ms 144512 KB 
#include <bits/stdc++.h>

typedef long long ll;

#define set set1

using namespace std;

const int N = 1e6 + 7;
const ll INF = 1e18 + 100;

ll mx[4 * N];
ll delta[4 * N];

void apply(int v, ll val) {
    mx[v] += val;
    delta[v] += val;
}

void push(int v) {
    apply(2 * v, delta[v]);
    apply(2 * v + 1, delta[v]);
    delta[v] = 0;
}

void modify(int v, int tl, int tr, int l, int r, ll val) {
    if (tl >= r || tr <= l)
        return;
    if (tl >= l && tr <= r) {
        apply(v, val);
        return;
    }
    push(v);
    int tm = (tl + tr) / 2;
    modify(2 * v, tl, tm, l, r, val);
    modify(2 * v + 1, tm, tr, l, r, val);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}

void set(int v, int l, int r, int pos, ll val) {
    if (r - l == 1) {
        mx[v] = max(mx[v], val);
    } else {
        push(v);
        int m = (l + r) / 2;
        if (pos < m)
            set(2 * v, l, m, pos, val);
        else 
            set(2 * v + 1, m, r, pos, val);
        mx[v] = max(mx[2 * v], mx[2 * v + 1]);
    }
}

ll query(int v, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l)
        return -INF;
    if (tl >= l && tr <= r)
        return mx[v];
    push(v);
    int tm = (tl + tr) / 2;
    return max(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm, tr, l, r));
}

int n, m;
ll a[N], b[N];
ll s[N], t[N];
ll p[N], q[N];

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> s[i] >> p[i];
        a[i] += a[i - 1];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> b[i] >> t[i] >> q[i];
        b[i] += b[i - 1];
    }
    ll sum = 0;
    vector<pair<pair<int, int>, ll>> events;
    for (int i = 1; i <= n; i++) {
        if (a[i] > s[i])
            continue;
        // cout << "Donburi " << i << endl;
        int ind = upper_bound(b, b + m + 1, s[i] - a[i]) - b - 1;
        if (ind == m)
            sum += p[i];
        else 
            events.push_back({{i, -ind}, p[i]});
    }
    for (int i = 1; i <= m; i++) {
        if (b[i] > t[i]) 
            continue;
        // cout << "Curry " << i << endl;
        int ind = upper_bound(a, a + n + 1, t[i] - b[i]) - a - 1;
        sum += q[i];
        if (ind != n)
            events.push_back({{ind + 1, -(i - 1)}, -q[i]});
    }
    sort(events.begin(), events.end());
    /* vector<pair<pair<int, int>, ll>> temp;
    for (auto &ev : events) {
        if (temp.empty() || ev.first != temp.back().first)
            temp.push_back(ev);
        else 
            temp.back().second += ev.second;
    }
    events = temp; */
    for (auto &ev : events) {
        int pos = -ev.first.second;
        ll val = ev.second;
        ll down = query(1, 0, m + 1, 0, pos + 1);
        modify(1, 0, m + 1, 0, pos + 1, val);
        if (pos != m)
            set(1, 0, m + 1, pos + 1, down);
        /* for (int i = 0; i <= m; i++) 
            cout << query(1, 0, m + 1, i, i + 1) << " ";
        cout << endl; */
    }
    cout << sum + mx[1] << endl;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 36688 KB Output is correct
2 Correct 516 ms 36176 KB Output is correct
3 Correct 183 ms 23148 KB Output is correct
4 Correct 407 ms 32476 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 452 ms 33616 KB Output is correct
7 Correct 86 ms 12012 KB Output is correct
8 Correct 88 ms 12140 KB Output is correct
9 Correct 187 ms 24212 KB Output is correct
10 Correct 505 ms 31952 KB Output is correct
11 Correct 129 ms 17516 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 3 ms 620 KB Output is correct
18 Correct 4 ms 748 KB Output is correct
19 Correct 5 ms 748 KB Output is correct
20 Correct 3 ms 748 KB Output is correct
21 Correct 4 ms 748 KB Output is correct
22 Correct 4 ms 748 KB Output is correct
23 Correct 4 ms 748 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 3 ms 620 KB Output is correct
18 Correct 4 ms 748 KB Output is correct
19 Correct 5 ms 748 KB Output is correct
20 Correct 3 ms 748 KB Output is correct
21 Correct 4 ms 748 KB Output is correct
22 Correct 4 ms 748 KB Output is correct
23 Correct 4 ms 748 KB Output is correct
24 Correct 289 ms 24548 KB Output is correct
25 Correct 319 ms 31836 KB Output is correct
26 Correct 320 ms 31964 KB Output is correct
27 Correct 327 ms 31964 KB Output is correct
28 Correct 280 ms 30692 KB Output is correct
29 Correct 155 ms 21228 KB Output is correct
30 Correct 686 ms 34896 KB Output is correct
31 Correct 159 ms 20312 KB Output is correct
32 Correct 86 ms 12520 KB Output is correct
33 Correct 396 ms 31444 KB Output is correct
34 Correct 558 ms 33360 KB Output is correct
35 Correct 621 ms 28752 KB Output is correct
36 Correct 625 ms 28496 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 3 ms 620 KB Output is correct
18 Correct 4 ms 748 KB Output is correct
19 Correct 5 ms 748 KB Output is correct
20 Correct 3 ms 748 KB Output is correct
21 Correct 4 ms 748 KB Output is correct
22 Correct 4 ms 748 KB Output is correct
23 Correct 4 ms 748 KB Output is correct
24 Correct 289 ms 24548 KB Output is correct
25 Correct 319 ms 31836 KB Output is correct
26 Correct 320 ms 31964 KB Output is correct
27 Correct 327 ms 31964 KB Output is correct
28 Correct 280 ms 30692 KB Output is correct
29 Correct 155 ms 21228 KB Output is correct
30 Correct 686 ms 34896 KB Output is correct
31 Correct 159 ms 20312 KB Output is correct
32 Correct 86 ms 12520 KB Output is correct
33 Correct 396 ms 31444 KB Output is correct
34 Correct 558 ms 33360 KB Output is correct
35 Correct 621 ms 28752 KB Output is correct
36 Correct 625 ms 28496 KB Output is correct
37 Correct 355 ms 34988 KB Output is correct
38 Correct 361 ms 35036 KB Output is correct
39 Correct 533 ms 35408 KB Output is correct
40 Correct 540 ms 35536 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 696 ms 38096 KB Output is correct
43 Correct 431 ms 34524 KB Output is correct
44 Correct 567 ms 36176 KB Output is correct
45 Correct 638 ms 31704 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 3 ms 620 KB Output is correct
18 Correct 4 ms 748 KB Output is correct
19 Correct 5 ms 748 KB Output is correct
20 Correct 3 ms 748 KB Output is correct
21 Correct 4 ms 748 KB Output is correct
22 Correct 4 ms 748 KB Output is correct
23 Correct 4 ms 748 KB Output is correct
24 Correct 289 ms 24548 KB Output is correct
25 Correct 319 ms 31836 KB Output is correct
26 Correct 320 ms 31964 KB Output is correct
27 Correct 327 ms 31964 KB Output is correct
28 Correct 280 ms 30692 KB Output is correct
29 Correct 155 ms 21228 KB Output is correct
30 Correct 686 ms 34896 KB Output is correct
31 Correct 159 ms 20312 KB Output is correct
32 Correct 86 ms 12520 KB Output is correct
33 Correct 396 ms 31444 KB Output is correct
34 Correct 558 ms 33360 KB Output is correct
35 Correct 621 ms 28752 KB Output is correct
36 Correct 625 ms 28496 KB Output is correct
37 Correct 355 ms 34988 KB Output is correct
38 Correct 361 ms 35036 KB Output is correct
39 Correct 533 ms 35408 KB Output is correct
40 Correct 540 ms 35536 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 696 ms 38096 KB Output is correct
43 Correct 431 ms 34524 KB Output is correct
44 Correct 567 ms 36176 KB Output is correct
45 Correct 638 ms 31704 KB Output is correct
46 Correct 1868 ms 133040 KB Output is correct
47 Correct 1854 ms 117584 KB Output is correct
48 Correct 2914 ms 134112 KB Output is correct
49 Correct 2924 ms 137008 KB Output is correct
50 Correct 4681 ms 132428 KB Output is correct
51 Correct 2619 ms 115680 KB Output is correct
52 Correct 3181 ms 120644 KB Output is correct
53 Correct 3985 ms 124724 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 36688 KB Output is correct
2 Correct 516 ms 36176 KB Output is correct
3 Correct 183 ms 23148 KB Output is correct
4 Correct 407 ms 32476 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 452 ms 33616 KB Output is correct
7 Correct 86 ms 12012 KB Output is correct
8 Correct 88 ms 12140 KB Output is correct
9 Correct 187 ms 24212 KB Output is correct
10 Correct 505 ms 31952 KB Output is correct
11 Correct 129 ms 17516 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 3 ms 620 KB Output is correct
29 Correct 4 ms 748 KB Output is correct
30 Correct 5 ms 748 KB Output is correct
31 Correct 3 ms 748 KB Output is correct
32 Correct 4 ms 748 KB Output is correct
33 Correct 4 ms 748 KB Output is correct
34 Correct 4 ms 748 KB Output is correct
35 Correct 289 ms 24548 KB Output is correct
36 Correct 319 ms 31836 KB Output is correct
37 Correct 320 ms 31964 KB Output is correct
38 Correct 327 ms 31964 KB Output is correct
39 Correct 280 ms 30692 KB Output is correct
40 Correct 155 ms 21228 KB Output is correct
41 Correct 686 ms 34896 KB Output is correct
42 Correct 159 ms 20312 KB Output is correct
43 Correct 86 ms 12520 KB Output is correct
44 Correct 396 ms 31444 KB Output is correct
45 Correct 558 ms 33360 KB Output is correct
46 Correct 621 ms 28752 KB Output is correct
47 Correct 625 ms 28496 KB Output is correct
48 Correct 355 ms 34988 KB Output is correct
49 Correct 361 ms 35036 KB Output is correct
50 Correct 533 ms 35408 KB Output is correct
51 Correct 540 ms 35536 KB Output is correct
52 Correct 1 ms 364 KB Output is correct
53 Correct 696 ms 38096 KB Output is correct
54 Correct 431 ms 34524 KB Output is correct
55 Correct 567 ms 36176 KB Output is correct
56 Correct 638 ms 31704 KB Output is correct
57 Correct 361 ms 35420 KB Output is correct
58 Correct 362 ms 35420 KB Output is correct
59 Correct 551 ms 36560 KB Output is correct
60 Correct 552 ms 36560 KB Output is correct
61 Correct 681 ms 35280 KB Output is correct
62 Correct 1 ms 364 KB Output is correct
63 Correct 690 ms 38096 KB Output is correct
64 Correct 428 ms 34396 KB Output is correct
65 Correct 572 ms 36432 KB Output is correct
66 Correct 625 ms 31696 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 36688 KB Output is correct
2 Correct 516 ms 36176 KB Output is correct
3 Correct 183 ms 23148 KB Output is correct
4 Correct 407 ms 32476 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 452 ms 33616 KB Output is correct
7 Correct 86 ms 12012 KB Output is correct
8 Correct 88 ms 12140 KB Output is correct
9 Correct 187 ms 24212 KB Output is correct
10 Correct 505 ms 31952 KB Output is correct
11 Correct 129 ms 17516 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 3 ms 620 KB Output is correct
29 Correct 4 ms 748 KB Output is correct
30 Correct 5 ms 748 KB Output is correct
31 Correct 3 ms 748 KB Output is correct
32 Correct 4 ms 748 KB Output is correct
33 Correct 4 ms 748 KB Output is correct
34 Correct 4 ms 748 KB Output is correct
35 Correct 289 ms 24548 KB Output is correct
36 Correct 319 ms 31836 KB Output is correct
37 Correct 320 ms 31964 KB Output is correct
38 Correct 327 ms 31964 KB Output is correct
39 Correct 280 ms 30692 KB Output is correct
40 Correct 155 ms 21228 KB Output is correct
41 Correct 686 ms 34896 KB Output is correct
42 Correct 159 ms 20312 KB Output is correct
43 Correct 86 ms 12520 KB Output is correct
44 Correct 396 ms 31444 KB Output is correct
45 Correct 558 ms 33360 KB Output is correct
46 Correct 621 ms 28752 KB Output is correct
47 Correct 625 ms 28496 KB Output is correct
48 Correct 355 ms 34988 KB Output is correct
49 Correct 361 ms 35036 KB Output is correct
50 Correct 533 ms 35408 KB Output is correct
51 Correct 540 ms 35536 KB Output is correct
52 Correct 1 ms 364 KB Output is correct
53 Correct 696 ms 38096 KB Output is correct
54 Correct 431 ms 34524 KB Output is correct
55 Correct 567 ms 36176 KB Output is correct
56 Correct 638 ms 31704 KB Output is correct
57 Correct 1868 ms 133040 KB Output is correct
58 Correct 1854 ms 117584 KB Output is correct
59 Correct 2914 ms 134112 KB Output is correct
60 Correct 2924 ms 137008 KB Output is correct
61 Correct 4681 ms 132428 KB Output is correct
62 Correct 2619 ms 115680 KB Output is correct
63 Correct 3181 ms 120644 KB Output is correct
64 Correct 3985 ms 124724 KB Output is correct
65 Correct 361 ms 35420 KB Output is correct
66 Correct 362 ms 35420 KB Output is correct
67 Correct 551 ms 36560 KB Output is correct
68 Correct 552 ms 36560 KB Output is correct
69 Correct 681 ms 35280 KB Output is correct
70 Correct 1 ms 364 KB Output is correct
71 Correct 690 ms 38096 KB Output is correct
72 Correct 428 ms 34396 KB Output is correct
73 Correct 572 ms 36432 KB Output is correct
74 Correct 625 ms 31696 KB Output is correct
75 Correct 1897 ms 127880 KB Output is correct
76 Correct 1940 ms 129736 KB Output is correct
77 Correct 2964 ms 138892 KB Output is correct
78 Correct 2979 ms 138828 KB Output is correct
79 Correct 4436 ms 144512 KB Output is correct
80 Correct 2561 ms 126984 KB Output is correct
81 Correct 3180 ms 133728 KB Output is correct
82 Correct 4158 ms 128888 KB Output is correct
83 Correct 4041 ms 137676 KB Output is correct