oj.uz

Submission #697146

# Submission time Handle Problem Language Result Execution time Memory
697146 2023-02-08T15:59:01 Z elkernos Two Dishes (JOI19_dishes) C++17
100 / 100
 4448 ms 247972 KB 
// while (clock()<=69*CLOCKS_PER_SEC)
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
// #pragma GCC target ("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                    \
    sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
    {
sim > struct rge {
    c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
    ~debug()
    {
        cerr << endl;
    }
    eni(!=) cerr << boolalpha << i;
    ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
    ris << "" << d.first << " --> " << d.second << "";
}
sim dor(rge<c> d)
{
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
    sim dor(const c &)
    {
        ris;
    }
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#ifdef XOX
#warning Times may differ!!!
#endif

#define endl '\n'
#define pb emplace_back
#define vt vector
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define int long long

const int oo = 1e18 + 123;
struct Node {
    int maxi;
    int lazy_sum, lazy_max;
};
#define md (l + r) / 2
#define lc 2 * v
#define rc 2 * v + 1

int m;
vector<Node> tree(1 << 21);

void pchaj(int v, int l, int r)
{
    auto &me = tree[v];
    me.maxi += me.lazy_sum;
    me.maxi = max(me.maxi, me.lazy_max);
    if (l != r) {
        auto &to_left = tree[lc];
        to_left.lazy_max = max(to_left.lazy_max + me.lazy_sum, me.lazy_max);
        to_left.lazy_sum += me.lazy_sum;
        auto &to_right = tree[rc];
        to_right.lazy_max = max(to_right.lazy_max + me.lazy_sum, me.lazy_max);
        to_right.lazy_sum += me.lazy_sum;
    }
    me.lazy_max = -oo, me.lazy_sum = 0;
}

int pyt(int ql, int qr, int l = 0, int r = m, int v = 1)
{
    pchaj(v, l, r);
    if (ql > r || qr < l) return -oo;
    if (ql <= l && qr >= r) return tree[v].maxi;
    return max(pyt(ql, qr, l, md, lc),
               pyt(ql, qr, md + 1, r, rc));
}

void pisz(int ql, int qr, int sum, int maxuj, int l = 0, int r = m, int v = 1)
{
    pchaj(v, l, r);
    if (ql > r || qr < l) return;
    auto &me = tree[v];
    if (ql <= l && qr >= r) {
        me.lazy_max = max(me.lazy_max, maxuj);
        me.lazy_max += sum;
        me.lazy_sum += sum;
        pchaj(v, l, r);
        return;
    }
    pisz(ql, qr, sum, maxuj, l, md, lc);
    pisz(ql, qr, sum, maxuj, md + 1, r, rc);
    assert(me.lazy_max == -oo && me.lazy_sum == 0);
    me.maxi = max(tree[lc].maxi, tree[rc].maxi);
}

#undef lc
#undef rc
#undef md

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n >> m;
    vector<int> a(n + 1), s(n + 1), p(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> s[i] >> p[i];
        a[i] += a[i - 1];
    }
    vector<int> b(m + 1), t(m + 1), q(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> b[i] >> t[i] >> q[i];
        b[i] += b[i - 1];
    }
    vector<vector<pair<int, int>>> events(n + 1);
    int add = 0;
    for (int i = 1; i <= n; i++) {
        int where = upper_bound(all(b), s[i] - a[i]) - b.begin();
        if (where >= 1) {
            if (where == m + 1) {
                add += p[i];
                debug() << "zawsze" imie(p[i]);
                continue;
            }
            events[i].push_back({where - 1, p[i]});
            debug() << "od a: " << i << ", " << where - 1 << ", " << p[i];
        }
    }
    for (int i = 1; i <= m; i++) {
        int where = upper_bound(all(a), t[i] - b[i]) - a.begin();
        if (where >= 1) {
            if (where == n + 1) {
                add += q[i];
                debug() << "zawsze" imie(q[i]);
                continue;
            }
            add += q[i];
            q[i] *= -1;
            events[where].push_back({i - 1, q[i]});
            debug() << "od b: " << where << ", " << i - 1 << ", " << q[i];
        }
    }
    for (int rep = 1; rep <= n; rep++) {
        sort(events[rep].begin(), events[rep].end(), [&](auto &i, auto &j) { // need
            return i.first == j.first ? i.second < j.second : i.first > j.first;
        });
        debug() << imie(events[rep]);
        for (auto [from, inc] : events[rep]) {
            // dodaj na [from, n] inc
            pisz(0, from, inc, -oo);
            int his_dp = pyt(0, from);
            debug() << imie(his_dp);
            pisz(from + 1, m, 0, his_dp);
        }
    }
    // add + wartosc w n
    cout << add + tree[1].maxi << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 73564 KB Output is correct
2 Correct 515 ms 73004 KB Output is correct
3 Correct 173 ms 77020 KB Output is correct
4 Correct 415 ms 83132 KB Output is correct
5 Correct 22 ms 49492 KB Output is correct
6 Correct 462 ms 84432 KB Output is correct
7 Correct 94 ms 61004 KB Output is correct
8 Correct 96 ms 65900 KB Output is correct
9 Correct 191 ms 78060 KB Output is correct
10 Correct 499 ms 80588 KB Output is correct
11 Correct 120 ms 71388 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49492 KB Output is correct
2 Correct 20 ms 49472 KB Output is correct
3 Correct 19 ms 49492 KB Output is correct
4 Correct 19 ms 49492 KB Output is correct
5 Correct 22 ms 49492 KB Output is correct
6 Correct 19 ms 49560 KB Output is correct
7 Correct 20 ms 49520 KB Output is correct
8 Correct 22 ms 49492 KB Output is correct
9 Correct 20 ms 49576 KB Output is correct
10 Correct 19 ms 49492 KB Output is correct
11 Correct 20 ms 49552 KB Output is correct
12 Correct 18 ms 49492 KB Output is correct
13 Correct 19 ms 49492 KB Output is correct
14 Correct 24 ms 49548 KB Output is correct
15 Correct 19 ms 49492 KB Output is correct
16 Correct 20 ms 49576 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49492 KB Output is correct
2 Correct 20 ms 49472 KB Output is correct
3 Correct 19 ms 49492 KB Output is correct
4 Correct 19 ms 49492 KB Output is correct
5 Correct 22 ms 49492 KB Output is correct
6 Correct 19 ms 49560 KB Output is correct
7 Correct 20 ms 49520 KB Output is correct
8 Correct 22 ms 49492 KB Output is correct
9 Correct 20 ms 49576 KB Output is correct
10 Correct 19 ms 49492 KB Output is correct
11 Correct 20 ms 49552 KB Output is correct
12 Correct 18 ms 49492 KB Output is correct
13 Correct 19 ms 49492 KB Output is correct
14 Correct 24 ms 49548 KB Output is correct
15 Correct 19 ms 49492 KB Output is correct
16 Correct 20 ms 49576 KB Output is correct
17 Correct 21 ms 49772 KB Output is correct
18 Correct 22 ms 49736 KB Output is correct
19 Correct 24 ms 49848 KB Output is correct
20 Correct 24 ms 49768 KB Output is correct
21 Correct 24 ms 49868 KB Output is correct
22 Correct 23 ms 49760 KB Output is correct
23 Correct 23 ms 49848 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49492 KB Output is correct
2 Correct 20 ms 49472 KB Output is correct
3 Correct 19 ms 49492 KB Output is correct
4 Correct 19 ms 49492 KB Output is correct
5 Correct 22 ms 49492 KB Output is correct
6 Correct 19 ms 49560 KB Output is correct
7 Correct 20 ms 49520 KB Output is correct
8 Correct 22 ms 49492 KB Output is correct
9 Correct 20 ms 49576 KB Output is correct
10 Correct 19 ms 49492 KB Output is correct
11 Correct 20 ms 49552 KB Output is correct
12 Correct 18 ms 49492 KB Output is correct
13 Correct 19 ms 49492 KB Output is correct
14 Correct 24 ms 49548 KB Output is correct
15 Correct 19 ms 49492 KB Output is correct
16 Correct 20 ms 49576 KB Output is correct
17 Correct 21 ms 49772 KB Output is correct
18 Correct 22 ms 49736 KB Output is correct
19 Correct 24 ms 49848 KB Output is correct
20 Correct 24 ms 49768 KB Output is correct
21 Correct 24 ms 49868 KB Output is correct
22 Correct 23 ms 49760 KB Output is correct
23 Correct 23 ms 49848 KB Output is correct
24 Correct 350 ms 80620 KB Output is correct
25 Correct 320 ms 78476 KB Output is correct
26 Correct 343 ms 80720 KB Output is correct
27 Correct 330 ms 80616 KB Output is correct
28 Correct 305 ms 77368 KB Output is correct
29 Correct 160 ms 74868 KB Output is correct
30 Correct 690 ms 85728 KB Output is correct
31 Correct 169 ms 61668 KB Output is correct
32 Correct 92 ms 67320 KB Output is correct
33 Correct 416 ms 79408 KB Output is correct
34 Correct 556 ms 82952 KB Output is correct
35 Correct 667 ms 79564 KB Output is correct
36 Correct 647 ms 79204 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49492 KB Output is correct
2 Correct 20 ms 49472 KB Output is correct
3 Correct 19 ms 49492 KB Output is correct
4 Correct 19 ms 49492 KB Output is correct
5 Correct 22 ms 49492 KB Output is correct
6 Correct 19 ms 49560 KB Output is correct
7 Correct 20 ms 49520 KB Output is correct
8 Correct 22 ms 49492 KB Output is correct
9 Correct 20 ms 49576 KB Output is correct
10 Correct 19 ms 49492 KB Output is correct
11 Correct 20 ms 49552 KB Output is correct
12 Correct 18 ms 49492 KB Output is correct
13 Correct 19 ms 49492 KB Output is correct
14 Correct 24 ms 49548 KB Output is correct
15 Correct 19 ms 49492 KB Output is correct
16 Correct 20 ms 49576 KB Output is correct
17 Correct 21 ms 49772 KB Output is correct
18 Correct 22 ms 49736 KB Output is correct
19 Correct 24 ms 49848 KB Output is correct
20 Correct 24 ms 49768 KB Output is correct
21 Correct 24 ms 49868 KB Output is correct
22 Correct 23 ms 49760 KB Output is correct
23 Correct 23 ms 49848 KB Output is correct
24 Correct 350 ms 80620 KB Output is correct
25 Correct 320 ms 78476 KB Output is correct
26 Correct 343 ms 80720 KB Output is correct
27 Correct 330 ms 80616 KB Output is correct
28 Correct 305 ms 77368 KB Output is correct
29 Correct 160 ms 74868 KB Output is correct
30 Correct 690 ms 85728 KB Output is correct
31 Correct 169 ms 61668 KB Output is correct
32 Correct 92 ms 67320 KB Output is correct
33 Correct 416 ms 79408 KB Output is correct
34 Correct 556 ms 82952 KB Output is correct
35 Correct 667 ms 79564 KB Output is correct
36 Correct 647 ms 79204 KB Output is correct
37 Correct 362 ms 83612 KB Output is correct
38 Correct 354 ms 83616 KB Output is correct
39 Correct 544 ms 84180 KB Output is correct
40 Correct 530 ms 84088 KB Output is correct
41 Correct 19 ms 49492 KB Output is correct
42 Correct 702 ms 88952 KB Output is correct
43 Correct 438 ms 82260 KB Output is correct
44 Correct 586 ms 85836 KB Output is correct
45 Correct 701 ms 82708 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49492 KB Output is correct
2 Correct 20 ms 49472 KB Output is correct
3 Correct 19 ms 49492 KB Output is correct
4 Correct 19 ms 49492 KB Output is correct
5 Correct 22 ms 49492 KB Output is correct
6 Correct 19 ms 49560 KB Output is correct
7 Correct 20 ms 49520 KB Output is correct
8 Correct 22 ms 49492 KB Output is correct
9 Correct 20 ms 49576 KB Output is correct
10 Correct 19 ms 49492 KB Output is correct
11 Correct 20 ms 49552 KB Output is correct
12 Correct 18 ms 49492 KB Output is correct
13 Correct 19 ms 49492 KB Output is correct
14 Correct 24 ms 49548 KB Output is correct
15 Correct 19 ms 49492 KB Output is correct
16 Correct 20 ms 49576 KB Output is correct
17 Correct 21 ms 49772 KB Output is correct
18 Correct 22 ms 49736 KB Output is correct
19 Correct 24 ms 49848 KB Output is correct
20 Correct 24 ms 49768 KB Output is correct
21 Correct 24 ms 49868 KB Output is correct
22 Correct 23 ms 49760 KB Output is correct
23 Correct 23 ms 49848 KB Output is correct
24 Correct 350 ms 80620 KB Output is correct
25 Correct 320 ms 78476 KB Output is correct
26 Correct 343 ms 80720 KB Output is correct
27 Correct 330 ms 80616 KB Output is correct
28 Correct 305 ms 77368 KB Output is correct
29 Correct 160 ms 74868 KB Output is correct
30 Correct 690 ms 85728 KB Output is correct
31 Correct 169 ms 61668 KB Output is correct
32 Correct 92 ms 67320 KB Output is correct
33 Correct 416 ms 79408 KB Output is correct
34 Correct 556 ms 82952 KB Output is correct
35 Correct 667 ms 79564 KB Output is correct
36 Correct 647 ms 79204 KB Output is correct
37 Correct 362 ms 83612 KB Output is correct
38 Correct 354 ms 83616 KB Output is correct
39 Correct 544 ms 84180 KB Output is correct
40 Correct 530 ms 84088 KB Output is correct
41 Correct 19 ms 49492 KB Output is correct
42 Correct 702 ms 88952 KB Output is correct
43 Correct 438 ms 82260 KB Output is correct
44 Correct 586 ms 85836 KB Output is correct
45 Correct 701 ms 82708 KB Output is correct
46 Correct 1858 ms 221284 KB Output is correct
47 Correct 1847 ms 221344 KB Output is correct
48 Correct 2746 ms 223416 KB Output is correct
49 Correct 2794 ms 223436 KB Output is correct
50 Correct 4448 ms 247972 KB Output is correct
51 Correct 2597 ms 210480 KB Output is correct
52 Correct 3102 ms 222432 KB Output is correct
53 Correct 4208 ms 214624 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 73564 KB Output is correct
2 Correct 515 ms 73004 KB Output is correct
3 Correct 173 ms 77020 KB Output is correct
4 Correct 415 ms 83132 KB Output is correct
5 Correct 22 ms 49492 KB Output is correct
6 Correct 462 ms 84432 KB Output is correct
7 Correct 94 ms 61004 KB Output is correct
8 Correct 96 ms 65900 KB Output is correct
9 Correct 191 ms 78060 KB Output is correct
10 Correct 499 ms 80588 KB Output is correct
11 Correct 120 ms 71388 KB Output is correct
12 Correct 19 ms 49492 KB Output is correct
13 Correct 20 ms 49472 KB Output is correct
14 Correct 19 ms 49492 KB Output is correct
15 Correct 19 ms 49492 KB Output is correct
16 Correct 22 ms 49492 KB Output is correct
17 Correct 19 ms 49560 KB Output is correct
18 Correct 20 ms 49520 KB Output is correct
19 Correct 22 ms 49492 KB Output is correct
20 Correct 20 ms 49576 KB Output is correct
21 Correct 19 ms 49492 KB Output is correct
22 Correct 20 ms 49552 KB Output is correct
23 Correct 18 ms 49492 KB Output is correct
24 Correct 19 ms 49492 KB Output is correct
25 Correct 24 ms 49548 KB Output is correct
26 Correct 19 ms 49492 KB Output is correct
27 Correct 20 ms 49576 KB Output is correct
28 Correct 21 ms 49772 KB Output is correct
29 Correct 22 ms 49736 KB Output is correct
30 Correct 24 ms 49848 KB Output is correct
31 Correct 24 ms 49768 KB Output is correct
32 Correct 24 ms 49868 KB Output is correct
33 Correct 23 ms 49760 KB Output is correct
34 Correct 23 ms 49848 KB Output is correct
35 Correct 350 ms 80620 KB Output is correct
36 Correct 320 ms 78476 KB Output is correct
37 Correct 343 ms 80720 KB Output is correct
38 Correct 330 ms 80616 KB Output is correct
39 Correct 305 ms 77368 KB Output is correct
40 Correct 160 ms 74868 KB Output is correct
41 Correct 690 ms 85728 KB Output is correct
42 Correct 169 ms 61668 KB Output is correct
43 Correct 92 ms 67320 KB Output is correct
44 Correct 416 ms 79408 KB Output is correct
45 Correct 556 ms 82952 KB Output is correct
46 Correct 667 ms 79564 KB Output is correct
47 Correct 647 ms 79204 KB Output is correct
48 Correct 362 ms 83612 KB Output is correct
49 Correct 354 ms 83616 KB Output is correct
50 Correct 544 ms 84180 KB Output is correct
51 Correct 530 ms 84088 KB Output is correct
52 Correct 19 ms 49492 KB Output is correct
53 Correct 702 ms 88952 KB Output is correct
54 Correct 438 ms 82260 KB Output is correct
55 Correct 586 ms 85836 KB Output is correct
56 Correct 701 ms 82708 KB Output is correct
57 Correct 376 ms 84080 KB Output is correct
58 Correct 368 ms 84092 KB Output is correct
59 Correct 560 ms 85176 KB Output is correct
60 Correct 538 ms 85124 KB Output is correct
61 Correct 735 ms 86256 KB Output is correct
62 Correct 21 ms 49492 KB Output is correct
63 Correct 739 ms 89044 KB Output is correct
64 Correct 431 ms 82376 KB Output is correct
65 Correct 579 ms 85628 KB Output is correct
66 Correct 684 ms 82412 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 73564 KB Output is correct
2 Correct 515 ms 73004 KB Output is correct
3 Correct 173 ms 77020 KB Output is correct
4 Correct 415 ms 83132 KB Output is correct
5 Correct 22 ms 49492 KB Output is correct
6 Correct 462 ms 84432 KB Output is correct
7 Correct 94 ms 61004 KB Output is correct
8 Correct 96 ms 65900 KB Output is correct
9 Correct 191 ms 78060 KB Output is correct
10 Correct 499 ms 80588 KB Output is correct
11 Correct 120 ms 71388 KB Output is correct
12 Correct 19 ms 49492 KB Output is correct
13 Correct 20 ms 49472 KB Output is correct
14 Correct 19 ms 49492 KB Output is correct
15 Correct 19 ms 49492 KB Output is correct
16 Correct 22 ms 49492 KB Output is correct
17 Correct 19 ms 49560 KB Output is correct
18 Correct 20 ms 49520 KB Output is correct
19 Correct 22 ms 49492 KB Output is correct
20 Correct 20 ms 49576 KB Output is correct
21 Correct 19 ms 49492 KB Output is correct
22 Correct 20 ms 49552 KB Output is correct
23 Correct 18 ms 49492 KB Output is correct
24 Correct 19 ms 49492 KB Output is correct
25 Correct 24 ms 49548 KB Output is correct
26 Correct 19 ms 49492 KB Output is correct
27 Correct 20 ms 49576 KB Output is correct
28 Correct 21 ms 49772 KB Output is correct
29 Correct 22 ms 49736 KB Output is correct
30 Correct 24 ms 49848 KB Output is correct
31 Correct 24 ms 49768 KB Output is correct
32 Correct 24 ms 49868 KB Output is correct
33 Correct 23 ms 49760 KB Output is correct
34 Correct 23 ms 49848 KB Output is correct
35 Correct 350 ms 80620 KB Output is correct
36 Correct 320 ms 78476 KB Output is correct
37 Correct 343 ms 80720 KB Output is correct
38 Correct 330 ms 80616 KB Output is correct
39 Correct 305 ms 77368 KB Output is correct
40 Correct 160 ms 74868 KB Output is correct
41 Correct 690 ms 85728 KB Output is correct
42 Correct 169 ms 61668 KB Output is correct
43 Correct 92 ms 67320 KB Output is correct
44 Correct 416 ms 79408 KB Output is correct
45 Correct 556 ms 82952 KB Output is correct
46 Correct 667 ms 79564 KB Output is correct
47 Correct 647 ms 79204 KB Output is correct
48 Correct 362 ms 83612 KB Output is correct
49 Correct 354 ms 83616 KB Output is correct
50 Correct 544 ms 84180 KB Output is correct
51 Correct 530 ms 84088 KB Output is correct
52 Correct 19 ms 49492 KB Output is correct
53 Correct 702 ms 88952 KB Output is correct
54 Correct 438 ms 82260 KB Output is correct
55 Correct 586 ms 85836 KB Output is correct
56 Correct 701 ms 82708 KB Output is correct
57 Correct 1858 ms 221284 KB Output is correct
58 Correct 1847 ms 221344 KB Output is correct
59 Correct 2746 ms 223416 KB Output is correct
60 Correct 2794 ms 223436 KB Output is correct
61 Correct 4448 ms 247972 KB Output is correct
62 Correct 2597 ms 210480 KB Output is correct
63 Correct 3102 ms 222432 KB Output is correct
64 Correct 4208 ms 214624 KB Output is correct
65 Correct 376 ms 84080 KB Output is correct
66 Correct 368 ms 84092 KB Output is correct
67 Correct 560 ms 85176 KB Output is correct
68 Correct 538 ms 85124 KB Output is correct
69 Correct 735 ms 86256 KB Output is correct
70 Correct 21 ms 49492 KB Output is correct
71 Correct 739 ms 89044 KB Output is correct
72 Correct 431 ms 82376 KB Output is correct
73 Correct 579 ms 85628 KB Output is correct
74 Correct 684 ms 82412 KB Output is correct
75 Correct 1873 ms 222504 KB Output is correct
76 Correct 1880 ms 222444 KB Output is correct
77 Correct 2801 ms 225472 KB Output is correct
78 Correct 2796 ms 225112 KB Output is correct
79 Correct 4434 ms 246996 KB Output is correct
80 Correct 2477 ms 212300 KB Output is correct
81 Correct 3197 ms 222484 KB Output is correct
82 Correct 4335 ms 215540 KB Output is correct
83 Correct 4160 ms 232168 KB Output is correct