oj.uz

Submission #781855

# Submission time Handle Problem Language Result Execution time Memory
781855 2023-07-13T12:01:01 Z TeaTime Two Dishes (JOI19_dishes) C++17
74 / 100
 5463 ms 390844 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;
typedef long double ld;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SZ = 1'000'100, INF = 2'000'000'000'000'000'000;

#define int ll

ll n, m;

struct el {
    ll a, s, p;
};

vector<el> vec1, vec2;
vector<ll> pref1, pref2;

struct point {
    ll x, y, val;
};

vector<point> blue, red;

ll seg[SZ * 8], psh[SZ * 8];

void push(int v) {
    seg[v * 2 + 1] += psh[v];
    seg[v * 2 + 2] += psh[v];

    psh[v * 2 + 1] += psh[v];
    psh[v * 2 + 2] += psh[v];

    psh[v] = 0;
}

void upd(int v, int l, int r, int askl, int askr, ll val) {
    push(v);
    if (l >= askr || r <= askl) return;

    if (askl <= l && r <= askr) {
        seg[v] += val;
        psh[v] += val;
        return;
    }

    int mid = (l + r) / 2;
    upd(v * 2 + 1, l, mid, askl, askr, val);
    upd(v * 2 + 2, mid, r, askl, askr, val);
    seg[v] = max(seg[v * 2 + 1], seg[v * 2 + 2]);
}

void upd(int v, int l, int r, int pos, ll val) {
    push(v);
    if (l == r - 1) {
        seg[v] = val;
    } else {
        int mid = (l + r) / 2;

        if (pos < mid) {
            upd(v * 2 + 1, l, mid, pos, val);
        } else {
            upd(v * 2 + 2, mid, r, pos, val);
        }

        seg[v] = max(seg[v * 2 + 1], seg[v * 2 + 2]);
    }
}

ll ask(int v, int l, int r, int askl, int askr) {
    push(v);
    if (l >= askr || r <= askl) return -INF;

    if (askl <= l && r <= askr) return seg[v];

    int mid = (l + r) / 2;
    return max(ask(v * 2 + 1, l, mid, askl, askr), ask(v * 2 + 2, mid, r, askl, askr));
}

vector<point> points[SZ];

bool cmp(point a, point b) {
    return a.y < b.y;
}

signed main() {
    fastInp;

    cin >> n >> m;

    vec1.resize(n);
    vec2.resize(m);

    pref1.push_back(0);
    for (auto &c : vec1) {
        cin >> c.a >> c.s >> c.p;
        pref1.push_back(pref1.back() + c.a);
    }

    pref2.push_back(0);
    for (auto &c : vec2) {
        cin >> c.a >> c.s >> c.p;
        pref2.push_back(pref2.back() + c.a);
    }

    for (int i = 0; i < SZ; i++) {
        seg[i] = -INF;
    }

    upd(0, 0, SZ, 0, 0);

    // x is vec1
    // y is vec2
    ll ans = 0, prefsum = 0;
    for (int i = 0; i < n; i++) {
        prefsum += vec1[i].a;

        ll left = vec1[i].s - prefsum;
        if (left < 0) continue;

        int ind = upper_bound(pref2.begin(), pref2.end(), left) - pref2.begin() - 1;
        assert(ind >= 0);

        blue.push_back({i + 1, ind, vec1[i].p}); // above or on the lattice path
    }

    prefsum = 0;

    for (int i = 0; i < m; i++) {
        prefsum += vec2[i].a;

        ll left = vec2[i].s - prefsum;
        if (left < 0) continue;

        int ind = upper_bound(pref1.begin(), pref1.end(), left) - pref1.begin() - 1;
        assert(ind >= 0);

        red.push_back({ind, i + 1, vec2[i].p}); // under or on the lattice path
        blue.push_back({ind + 1, i, -vec2[i].p}); // above or on the lattice path
        ans += vec2[i].p;
    }

    for (auto c : blue) {
        points[c.x].push_back(c);
        if (c.x != 0) points[c.x - 1].push_back({c.x - 1, c.y + 1, 0});
    }

    for (int i = 0; i < SZ; i++) {
        sort(points[i].begin(), points[i].end(), cmp);

        vector<point> cur;
        for (auto c : points[i]) {
            if (!cur.empty() && cur.back().y == c.y) {
                cur.back().val += c.val;
            } else {
                cur.push_back(c);
            }
        }

        points[i] = cur;

        for (auto c : points[i]) {
            upd(0, 0, SZ, 0, c.y + 1, c.val);
            ll q = ask(0, 0, SZ, 0, c.y + 1);
            upd(0, 0, SZ, c.y, q);
        }
    }

    cout << ans + ask(0, 0, SZ, 0, SZ);

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 92520 KB Output is correct
2 Correct 454 ms 97724 KB Output is correct
3 Correct 622 ms 105632 KB Output is correct
4 Correct 286 ms 74176 KB Output is correct
5 Correct 19 ms 31736 KB Output is correct
6 Correct 474 ms 96648 KB Output is correct
7 Correct 315 ms 78044 KB Output is correct
8 Correct 337 ms 55680 KB Output is correct
9 Correct 625 ms 105616 KB Output is correct
10 Correct 301 ms 92220 KB Output is correct
11 Correct 654 ms 105256 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31700 KB Output is correct
2 Correct 24 ms 31700 KB Output is correct
3 Correct 23 ms 31628 KB Output is correct
4 Correct 21 ms 31700 KB Output is correct
5 Correct 21 ms 31740 KB Output is correct
6 Correct 19 ms 31616 KB Output is correct
7 Correct 19 ms 31624 KB Output is correct
8 Correct 20 ms 31632 KB Output is correct
9 Correct 19 ms 31700 KB Output is correct
10 Correct 19 ms 31620 KB Output is correct
11 Correct 19 ms 31700 KB Output is correct
12 Correct 20 ms 31624 KB Output is correct
13 Correct 20 ms 31700 KB Output is correct
14 Correct 24 ms 31700 KB Output is correct
15 Correct 22 ms 31700 KB Output is correct
16 Correct 19 ms 31700 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31700 KB Output is correct
2 Correct 24 ms 31700 KB Output is correct
3 Correct 23 ms 31628 KB Output is correct
4 Correct 21 ms 31700 KB Output is correct
5 Correct 21 ms 31740 KB Output is correct
6 Correct 19 ms 31616 KB Output is correct
7 Correct 19 ms 31624 KB Output is correct
8 Correct 20 ms 31632 KB Output is correct
9 Correct 19 ms 31700 KB Output is correct
10 Correct 19 ms 31620 KB Output is correct
11 Correct 19 ms 31700 KB Output is correct
12 Correct 20 ms 31624 KB Output is correct
13 Correct 20 ms 31700 KB Output is correct
14 Correct 24 ms 31700 KB Output is correct
15 Correct 22 ms 31700 KB Output is correct
16 Correct 19 ms 31700 KB Output is correct
17 Correct 25 ms 32288 KB Output is correct
18 Correct 33 ms 32452 KB Output is correct
19 Correct 30 ms 32384 KB Output is correct
20 Correct 24 ms 32212 KB Output is correct
21 Correct 27 ms 32468 KB Output is correct
22 Correct 33 ms 32404 KB Output is correct
23 Correct 33 ms 32404 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31700 KB Output is correct
2 Correct 24 ms 31700 KB Output is correct
3 Correct 23 ms 31628 KB Output is correct
4 Correct 21 ms 31700 KB Output is correct
5 Correct 21 ms 31740 KB Output is correct
6 Correct 19 ms 31616 KB Output is correct
7 Correct 19 ms 31624 KB Output is correct
8 Correct 20 ms 31632 KB Output is correct
9 Correct 19 ms 31700 KB Output is correct
10 Correct 19 ms 31620 KB Output is correct
11 Correct 19 ms 31700 KB Output is correct
12 Correct 20 ms 31624 KB Output is correct
13 Correct 20 ms 31700 KB Output is correct
14 Correct 24 ms 31700 KB Output is correct
15 Correct 22 ms 31700 KB Output is correct
16 Correct 19 ms 31700 KB Output is correct
17 Correct 25 ms 32288 KB Output is correct
18 Correct 33 ms 32452 KB Output is correct
19 Correct 30 ms 32384 KB Output is correct
20 Correct 24 ms 32212 KB Output is correct
21 Correct 27 ms 32468 KB Output is correct
22 Correct 33 ms 32404 KB Output is correct
23 Correct 33 ms 32404 KB Output is correct
24 Correct 528 ms 99308 KB Output is correct
25 Correct 516 ms 107068 KB Output is correct
26 Correct 527 ms 99496 KB Output is correct
27 Correct 511 ms 98688 KB Output is correct
28 Correct 669 ms 107840 KB Output is correct
29 Correct 633 ms 116392 KB Output is correct
30 Correct 892 ms 110160 KB Output is correct
31 Correct 298 ms 87004 KB Output is correct
32 Correct 302 ms 60364 KB Output is correct
33 Correct 486 ms 87224 KB Output is correct
34 Correct 790 ms 108244 KB Output is correct
35 Correct 827 ms 104148 KB Output is correct
36 Correct 827 ms 103392 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31700 KB Output is correct
2 Correct 24 ms 31700 KB Output is correct
3 Correct 23 ms 31628 KB Output is correct
4 Correct 21 ms 31700 KB Output is correct
5 Correct 21 ms 31740 KB Output is correct
6 Correct 19 ms 31616 KB Output is correct
7 Correct 19 ms 31624 KB Output is correct
8 Correct 20 ms 31632 KB Output is correct
9 Correct 19 ms 31700 KB Output is correct
10 Correct 19 ms 31620 KB Output is correct
11 Correct 19 ms 31700 KB Output is correct
12 Correct 20 ms 31624 KB Output is correct
13 Correct 20 ms 31700 KB Output is correct
14 Correct 24 ms 31700 KB Output is correct
15 Correct 22 ms 31700 KB Output is correct
16 Correct 19 ms 31700 KB Output is correct
17 Correct 25 ms 32288 KB Output is correct
18 Correct 33 ms 32452 KB Output is correct
19 Correct 30 ms 32384 KB Output is correct
20 Correct 24 ms 32212 KB Output is correct
21 Correct 27 ms 32468 KB Output is correct
22 Correct 33 ms 32404 KB Output is correct
23 Correct 33 ms 32404 KB Output is correct
24 Correct 528 ms 99308 KB Output is correct
25 Correct 516 ms 107068 KB Output is correct
26 Correct 527 ms 99496 KB Output is correct
27 Correct 511 ms 98688 KB Output is correct
28 Correct 669 ms 107840 KB Output is correct
29 Correct 633 ms 116392 KB Output is correct
30 Correct 892 ms 110160 KB Output is correct
31 Correct 298 ms 87004 KB Output is correct
32 Correct 302 ms 60364 KB Output is correct
33 Correct 486 ms 87224 KB Output is correct
34 Correct 790 ms 108244 KB Output is correct
35 Correct 827 ms 104148 KB Output is correct
36 Correct 827 ms 103392 KB Output is correct
37 Correct 453 ms 102568 KB Output is correct
38 Correct 405 ms 101644 KB Output is correct
39 Correct 310 ms 102832 KB Output is correct
40 Correct 297 ms 102856 KB Output is correct
41 Correct 19 ms 31700 KB Output is correct
42 Correct 908 ms 113228 KB Output is correct
43 Correct 508 ms 90164 KB Output is correct
44 Correct 803 ms 110800 KB Output is correct
45 Correct 938 ms 107192 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31700 KB Output is correct
2 Correct 24 ms 31700 KB Output is correct
3 Correct 23 ms 31628 KB Output is correct
4 Correct 21 ms 31700 KB Output is correct
5 Correct 21 ms 31740 KB Output is correct
6 Correct 19 ms 31616 KB Output is correct
7 Correct 19 ms 31624 KB Output is correct
8 Correct 20 ms 31632 KB Output is correct
9 Correct 19 ms 31700 KB Output is correct
10 Correct 19 ms 31620 KB Output is correct
11 Correct 19 ms 31700 KB Output is correct
12 Correct 20 ms 31624 KB Output is correct
13 Correct 20 ms 31700 KB Output is correct
14 Correct 24 ms 31700 KB Output is correct
15 Correct 22 ms 31700 KB Output is correct
16 Correct 19 ms 31700 KB Output is correct
17 Correct 25 ms 32288 KB Output is correct
18 Correct 33 ms 32452 KB Output is correct
19 Correct 30 ms 32384 KB Output is correct
20 Correct 24 ms 32212 KB Output is correct
21 Correct 27 ms 32468 KB Output is correct
22 Correct 33 ms 32404 KB Output is correct
23 Correct 33 ms 32404 KB Output is correct
24 Correct 528 ms 99308 KB Output is correct
25 Correct 516 ms 107068 KB Output is correct
26 Correct 527 ms 99496 KB Output is correct
27 Correct 511 ms 98688 KB Output is correct
28 Correct 669 ms 107840 KB Output is correct
29 Correct 633 ms 116392 KB Output is correct
30 Correct 892 ms 110160 KB Output is correct
31 Correct 298 ms 87004 KB Output is correct
32 Correct 302 ms 60364 KB Output is correct
33 Correct 486 ms 87224 KB Output is correct
34 Correct 790 ms 108244 KB Output is correct
35 Correct 827 ms 104148 KB Output is correct
36 Correct 827 ms 103392 KB Output is correct
37 Correct 453 ms 102568 KB Output is correct
38 Correct 405 ms 101644 KB Output is correct
39 Correct 310 ms 102832 KB Output is correct
40 Correct 297 ms 102856 KB Output is correct
41 Correct 19 ms 31700 KB Output is correct
42 Correct 908 ms 113228 KB Output is correct
43 Correct 508 ms 90164 KB Output is correct
44 Correct 803 ms 110800 KB Output is correct
45 Correct 938 ms 107192 KB Output is correct
46 Correct 2144 ms 331628 KB Output is correct
47 Correct 2078 ms 331340 KB Output is correct
48 Correct 1463 ms 346028 KB Output is correct
49 Correct 1456 ms 345876 KB Output is correct
50 Correct 5463 ms 390844 KB Output is correct
51 Correct 3200 ms 271528 KB Output is correct
52 Correct 4286 ms 365516 KB Output is correct
53 Correct 5145 ms 375820 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 92520 KB Output is correct
2 Correct 454 ms 97724 KB Output is correct
3 Correct 622 ms 105632 KB Output is correct
4 Correct 286 ms 74176 KB Output is correct
5 Correct 19 ms 31736 KB Output is correct
6 Correct 474 ms 96648 KB Output is correct
7 Correct 315 ms 78044 KB Output is correct
8 Correct 337 ms 55680 KB Output is correct
9 Correct 625 ms 105616 KB Output is correct
10 Correct 301 ms 92220 KB Output is correct
11 Correct 654 ms 105256 KB Output is correct
12 Correct 21 ms 31700 KB Output is correct
13 Correct 24 ms 31700 KB Output is correct
14 Correct 23 ms 31628 KB Output is correct
15 Correct 21 ms 31700 KB Output is correct
16 Correct 21 ms 31740 KB Output is correct
17 Correct 19 ms 31616 KB Output is correct
18 Correct 19 ms 31624 KB Output is correct
19 Correct 20 ms 31632 KB Output is correct
20 Correct 19 ms 31700 KB Output is correct
21 Correct 19 ms 31620 KB Output is correct
22 Correct 19 ms 31700 KB Output is correct
23 Correct 20 ms 31624 KB Output is correct
24 Correct 20 ms 31700 KB Output is correct
25 Correct 24 ms 31700 KB Output is correct
26 Correct 22 ms 31700 KB Output is correct
27 Correct 19 ms 31700 KB Output is correct
28 Correct 25 ms 32288 KB Output is correct
29 Correct 33 ms 32452 KB Output is correct
30 Correct 30 ms 32384 KB Output is correct
31 Correct 24 ms 32212 KB Output is correct
32 Correct 27 ms 32468 KB Output is correct
33 Correct 33 ms 32404 KB Output is correct
34 Correct 33 ms 32404 KB Output is correct
35 Correct 528 ms 99308 KB Output is correct
36 Correct 516 ms 107068 KB Output is correct
37 Correct 527 ms 99496 KB Output is correct
38 Correct 511 ms 98688 KB Output is correct
39 Correct 669 ms 107840 KB Output is correct
40 Correct 633 ms 116392 KB Output is correct
41 Correct 892 ms 110160 KB Output is correct
42 Correct 298 ms 87004 KB Output is correct
43 Correct 302 ms 60364 KB Output is correct
44 Correct 486 ms 87224 KB Output is correct
45 Correct 790 ms 108244 KB Output is correct
46 Correct 827 ms 104148 KB Output is correct
47 Correct 827 ms 103392 KB Output is correct
48 Correct 453 ms 102568 KB Output is correct
49 Correct 405 ms 101644 KB Output is correct
50 Correct 310 ms 102832 KB Output is correct
51 Correct 297 ms 102856 KB Output is correct
52 Correct 19 ms 31700 KB Output is correct
53 Correct 908 ms 113228 KB Output is correct
54 Correct 508 ms 90164 KB Output is correct
55 Correct 803 ms 110800 KB Output is correct
56 Correct 938 ms 107192 KB Output is correct
57 Incorrect 549 ms 103012 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 92520 KB Output is correct
2 Correct 454 ms 97724 KB Output is correct
3 Correct 622 ms 105632 KB Output is correct
4 Correct 286 ms 74176 KB Output is correct
5 Correct 19 ms 31736 KB Output is correct
6 Correct 474 ms 96648 KB Output is correct
7 Correct 315 ms 78044 KB Output is correct
8 Correct 337 ms 55680 KB Output is correct
9 Correct 625 ms 105616 KB Output is correct
10 Correct 301 ms 92220 KB Output is correct
11 Correct 654 ms 105256 KB Output is correct
12 Correct 21 ms 31700 KB Output is correct
13 Correct 24 ms 31700 KB Output is correct
14 Correct 23 ms 31628 KB Output is correct
15 Correct 21 ms 31700 KB Output is correct
16 Correct 21 ms 31740 KB Output is correct
17 Correct 19 ms 31616 KB Output is correct
18 Correct 19 ms 31624 KB Output is correct
19 Correct 20 ms 31632 KB Output is correct
20 Correct 19 ms 31700 KB Output is correct
21 Correct 19 ms 31620 KB Output is correct
22 Correct 19 ms 31700 KB Output is correct
23 Correct 20 ms 31624 KB Output is correct
24 Correct 20 ms 31700 KB Output is correct
25 Correct 24 ms 31700 KB Output is correct
26 Correct 22 ms 31700 KB Output is correct
27 Correct 19 ms 31700 KB Output is correct
28 Correct 25 ms 32288 KB Output is correct
29 Correct 33 ms 32452 KB Output is correct
30 Correct 30 ms 32384 KB Output is correct
31 Correct 24 ms 32212 KB Output is correct
32 Correct 27 ms 32468 KB Output is correct
33 Correct 33 ms 32404 KB Output is correct
34 Correct 33 ms 32404 KB Output is correct
35 Correct 528 ms 99308 KB Output is correct
36 Correct 516 ms 107068 KB Output is correct
37 Correct 527 ms 99496 KB Output is correct
38 Correct 511 ms 98688 KB Output is correct
39 Correct 669 ms 107840 KB Output is correct
40 Correct 633 ms 116392 KB Output is correct
41 Correct 892 ms 110160 KB Output is correct
42 Correct 298 ms 87004 KB Output is correct
43 Correct 302 ms 60364 KB Output is correct
44 Correct 486 ms 87224 KB Output is correct
45 Correct 790 ms 108244 KB Output is correct
46 Correct 827 ms 104148 KB Output is correct
47 Correct 827 ms 103392 KB Output is correct
48 Correct 453 ms 102568 KB Output is correct
49 Correct 405 ms 101644 KB Output is correct
50 Correct 310 ms 102832 KB Output is correct
51 Correct 297 ms 102856 KB Output is correct
52 Correct 19 ms 31700 KB Output is correct
53 Correct 908 ms 113228 KB Output is correct
54 Correct 508 ms 90164 KB Output is correct
55 Correct 803 ms 110800 KB Output is correct
56 Correct 938 ms 107192 KB Output is correct
57 Correct 2144 ms 331628 KB Output is correct
58 Correct 2078 ms 331340 KB Output is correct
59 Correct 1463 ms 346028 KB Output is correct
60 Correct 1456 ms 345876 KB Output is correct
61 Correct 5463 ms 390844 KB Output is correct
62 Correct 3200 ms 271528 KB Output is correct
63 Correct 4286 ms 365516 KB Output is correct
64 Correct 5145 ms 375820 KB Output is correct
65 Incorrect 549 ms 103012 KB Output isn't correct
66 Halted 0 ms 0 KB -