oj.uz

Submission #166516

# Submission time Handle Problem Language Result Execution time Memory
166516 2019-12-02T16:20:36 Z Akashi Two Dishes (JOI19_dishes) C++14
100 / 100
 6832 ms 240672 KB 
#include <bits/stdc++.h>
using namespace std;

const int SZ = 1e6 + 5;
const long long INF = 1e18;

int n, m;
long long Arb[4000015], Lazy_scad[4000015], Lazy_max[4000015];

long long a[SZ], b[SZ], s[SZ], s1[SZ], s2[SZ], t[SZ], q[SZ], p[SZ];

void propag_scad(int nod){
    if(Lazy_scad[nod] != 0){
        Arb[nod * 2] += Lazy_scad[nod];
        Arb[nod * 2 + 1] += Lazy_scad[nod];
        Lazy_scad[nod * 2] += Lazy_scad[nod];
        Lazy_scad[nod * 2 + 1] += Lazy_scad[nod];
        Lazy_max[nod * 2] += Lazy_scad[nod];
        Lazy_max[nod * 2 + 1] += Lazy_scad[nod];
        Lazy_scad[nod] = 0;
    }
}

void propag_max(int nod){
    if(Lazy_max[nod] != -INF){
        Arb[nod * 2] = max(Arb[nod * 2], Lazy_max[nod]);
        Arb[nod * 2 + 1] = max(Arb[nod * 2 + 1], Lazy_max[nod]);

        Lazy_max[nod * 2] = max(Lazy_max[nod * 2], Lazy_max[nod]);
        Lazy_max[nod * 2 + 1] = max(Lazy_max[nod * 2 + 1], Lazy_max[nod]);

        Lazy_max[nod] = -INF;
    }
}

void update_scad(int x, int y, long long v, int st = 0, int dr = m, int nod = 1){
    if(st != dr) propag_scad(nod), propag_max(nod);

    if(x <= st && dr <= y){
        Lazy_scad[nod] += v;
        Arb[nod] += v;
        return ;
    }

    int mij = (st + dr) / 2;
    if(x <= mij) update_scad(x, y, v, st, mij, nod * 2);
    if(mij + 1 <= y) update_scad(x, y, v, mij + 1, dr, nod * 2 + 1);

    Arb[nod] = max(Arb[nod * 2], Arb[nod * 2 + 1]);
}

void update_max(int x, int y, long long v, int st = 0, int dr = m, int nod = 1){
    if(st != dr) propag_scad(nod), propag_max(nod);

    if(x <= st && dr <= y){
        Lazy_max[nod] = max(v, Lazy_max[nod]);
        Arb[nod] = max(v, Arb[nod]);
        return ;
    }

    int mij = (st + dr) / 2;
    if(x <= mij) update_max(x, y, v, st, mij, nod * 2);
    if(mij + 1 <= y) update_max(x, y, v, mij + 1, dr, nod * 2 + 1);

    Arb[nod] = max(Arb[nod * 2], Arb[nod * 2 + 1]);
}

long long query(int x, int y, int st = 0, int dr = m, int nod = 1){
    if(x <= st && dr <= y) return Arb[nod];
    if(st != dr) propag_scad(nod), propag_max(nod);

    int mij = (st + dr) / 2;
    long long a1 = -INF, a2 = -INF;

    if(x <= mij) a1 = query(x, y, st, mij, nod * 2);
    if(mij + 1 <= y) a2 = query(x, y, mij + 1, dr, nod * 2 + 1);

    return max(a1, a2);
}

vector <pair <int, long long> > v[SZ];

void add_point(int x, int y, long long val){
    v[x].push_back({y, val});
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= 4000014 ; ++i) Lazy_max[i] = -INF;

    for(int i = 1; i <= n ; ++i){
        scanf("%lld%lld%lld", &a[i], &s[i], &p[i]);
        s1[i] = s1[i - 1] + a[i];
    }

    for(int i = 1; i <= m ; ++i){
        scanf("%lld%lld%lld", &b[i], &t[i], &q[i]);
        s2[i] = s2[i - 1] + b[i];
    }

    long long Sum = 0;
    for(int i = 1; i <= n ; ++i){
        long long v = s[i] - s1[i];
        if(v < 0) continue ;

        int st = 1, dr = m;
        while(st <= dr){
            int mij = (st + dr) / 2;

            if(s2[mij] <= v) st = mij + 1;
            else dr = mij - 1;
        }

        if(dr < m) add_point(i - 1, dr + 1, -p[i]);
        Sum += p[i];
    }

    for(int i = 1; i <= m ; ++i){
        long long v = t[i] - s2[i];
        if(v < 0) continue ;

        int st = 1, dr = n;
        while(st <= dr){
            int mij = (st + dr) / 2;

            if(s1[mij] <= v) st = mij + 1;
            else dr = mij - 1;
        }

        add_point(dr, i, q[i]);
    }

    for(int i = 0; i <= n ; ++i){
        if(i > 0){
            for(auto it : v[i - 1]){
                long long val = query(0, it.first);
                update_max(it.first, m, val);
            }
        }

        for(auto it : v[i]) update_scad(it.first, m, it.second);
    }

    long long val = query(m, m);
    printf("%lld", Sum + val);

    return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld", &a[i], &s[i], &p[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld", &b[i], &t[i], &q[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 98796 KB Output is correct
2 Correct 648 ms 99524 KB Output is correct
3 Correct 369 ms 92636 KB Output is correct
4 Correct 532 ms 92372 KB Output is correct
5 Correct 50 ms 55160 KB Output is correct
6 Correct 588 ms 97472 KB Output is correct
7 Correct 240 ms 78608 KB Output is correct
8 Correct 169 ms 68400 KB Output is correct
9 Correct 376 ms 93632 KB Output is correct
10 Correct 610 ms 92844 KB Output is correct
11 Correct 311 ms 86916 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 55160 KB Output is correct
2 Correct 134 ms 55160 KB Output is correct
3 Correct 56 ms 55160 KB Output is correct
4 Correct 55 ms 55212 KB Output is correct
5 Correct 56 ms 55160 KB Output is correct
6 Correct 57 ms 55164 KB Output is correct
7 Correct 57 ms 55160 KB Output is correct
8 Correct 57 ms 55160 KB Output is correct
9 Correct 50 ms 55220 KB Output is correct
10 Correct 51 ms 55160 KB Output is correct
11 Correct 56 ms 55160 KB Output is correct
12 Correct 51 ms 55160 KB Output is correct
13 Correct 56 ms 55160 KB Output is correct
14 Correct 50 ms 55160 KB Output is correct
15 Correct 54 ms 55160 KB Output is correct
16 Correct 52 ms 55316 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 55160 KB Output is correct
2 Correct 134 ms 55160 KB Output is correct
3 Correct 56 ms 55160 KB Output is correct
4 Correct 55 ms 55212 KB Output is correct
5 Correct 56 ms 55160 KB Output is correct
6 Correct 57 ms 55164 KB Output is correct
7 Correct 57 ms 55160 KB Output is correct
8 Correct 57 ms 55160 KB Output is correct
9 Correct 50 ms 55220 KB Output is correct
10 Correct 51 ms 55160 KB Output is correct
11 Correct 56 ms 55160 KB Output is correct
12 Correct 51 ms 55160 KB Output is correct
13 Correct 56 ms 55160 KB Output is correct
14 Correct 50 ms 55160 KB Output is correct
15 Correct 54 ms 55160 KB Output is correct
16 Correct 52 ms 55316 KB Output is correct
17 Correct 54 ms 55580 KB Output is correct
18 Correct 53 ms 55548 KB Output is correct
19 Correct 56 ms 55640 KB Output is correct
20 Correct 53 ms 55544 KB Output is correct
21 Correct 55 ms 55628 KB Output is correct
22 Correct 58 ms 55560 KB Output is correct
23 Correct 55 ms 55596 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 55160 KB Output is correct
2 Correct 134 ms 55160 KB Output is correct
3 Correct 56 ms 55160 KB Output is correct
4 Correct 55 ms 55212 KB Output is correct
5 Correct 56 ms 55160 KB Output is correct
6 Correct 57 ms 55164 KB Output is correct
7 Correct 57 ms 55160 KB Output is correct
8 Correct 57 ms 55160 KB Output is correct
9 Correct 50 ms 55220 KB Output is correct
10 Correct 51 ms 55160 KB Output is correct
11 Correct 56 ms 55160 KB Output is correct
12 Correct 51 ms 55160 KB Output is correct
13 Correct 56 ms 55160 KB Output is correct
14 Correct 50 ms 55160 KB Output is correct
15 Correct 54 ms 55160 KB Output is correct
16 Correct 52 ms 55316 KB Output is correct
17 Correct 54 ms 55580 KB Output is correct
18 Correct 53 ms 55548 KB Output is correct
19 Correct 56 ms 55640 KB Output is correct
20 Correct 53 ms 55544 KB Output is correct
21 Correct 55 ms 55628 KB Output is correct
22 Correct 58 ms 55560 KB Output is correct
23 Correct 55 ms 55596 KB Output is correct
24 Correct 551 ms 94332 KB Output is correct
25 Correct 452 ms 89796 KB Output is correct
26 Correct 510 ms 94480 KB Output is correct
27 Correct 473 ms 92924 KB Output is correct
28 Correct 532 ms 91616 KB Output is correct
29 Correct 332 ms 90448 KB Output is correct
30 Correct 1076 ms 97956 KB Output is correct
31 Correct 287 ms 78284 KB Output is correct
32 Correct 168 ms 69852 KB Output is correct
33 Correct 648 ms 91812 KB Output is correct
34 Correct 863 ms 95572 KB Output is correct
35 Correct 977 ms 91980 KB Output is correct
36 Correct 955 ms 91608 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 55160 KB Output is correct
2 Correct 134 ms 55160 KB Output is correct
3 Correct 56 ms 55160 KB Output is correct
4 Correct 55 ms 55212 KB Output is correct
5 Correct 56 ms 55160 KB Output is correct
6 Correct 57 ms 55164 KB Output is correct
7 Correct 57 ms 55160 KB Output is correct
8 Correct 57 ms 55160 KB Output is correct
9 Correct 50 ms 55220 KB Output is correct
10 Correct 51 ms 55160 KB Output is correct
11 Correct 56 ms 55160 KB Output is correct
12 Correct 51 ms 55160 KB Output is correct
13 Correct 56 ms 55160 KB Output is correct
14 Correct 50 ms 55160 KB Output is correct
15 Correct 54 ms 55160 KB Output is correct
16 Correct 52 ms 55316 KB Output is correct
17 Correct 54 ms 55580 KB Output is correct
18 Correct 53 ms 55548 KB Output is correct
19 Correct 56 ms 55640 KB Output is correct
20 Correct 53 ms 55544 KB Output is correct
21 Correct 55 ms 55628 KB Output is correct
22 Correct 58 ms 55560 KB Output is correct
23 Correct 55 ms 55596 KB Output is correct
24 Correct 551 ms 94332 KB Output is correct
25 Correct 452 ms 89796 KB Output is correct
26 Correct 510 ms 94480 KB Output is correct
27 Correct 473 ms 92924 KB Output is correct
28 Correct 532 ms 91616 KB Output is correct
29 Correct 332 ms 90448 KB Output is correct
30 Correct 1076 ms 97956 KB Output is correct
31 Correct 287 ms 78284 KB Output is correct
32 Correct 168 ms 69852 KB Output is correct
33 Correct 648 ms 91812 KB Output is correct
34 Correct 863 ms 95572 KB Output is correct
35 Correct 977 ms 91980 KB Output is correct
36 Correct 955 ms 91608 KB Output is correct
37 Correct 542 ms 94476 KB Output is correct
38 Correct 517 ms 95784 KB Output is correct
39 Correct 652 ms 96356 KB Output is correct
40 Correct 663 ms 96356 KB Output is correct
41 Correct 50 ms 55160 KB Output is correct
42 Correct 1087 ms 98052 KB Output is correct
43 Correct 692 ms 94832 KB Output is correct
44 Correct 898 ms 96944 KB Output is correct
45 Correct 1026 ms 95088 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 55160 KB Output is correct
2 Correct 134 ms 55160 KB Output is correct
3 Correct 56 ms 55160 KB Output is correct
4 Correct 55 ms 55212 KB Output is correct
5 Correct 56 ms 55160 KB Output is correct
6 Correct 57 ms 55164 KB Output is correct
7 Correct 57 ms 55160 KB Output is correct
8 Correct 57 ms 55160 KB Output is correct
9 Correct 50 ms 55220 KB Output is correct
10 Correct 51 ms 55160 KB Output is correct
11 Correct 56 ms 55160 KB Output is correct
12 Correct 51 ms 55160 KB Output is correct
13 Correct 56 ms 55160 KB Output is correct
14 Correct 50 ms 55160 KB Output is correct
15 Correct 54 ms 55160 KB Output is correct
16 Correct 52 ms 55316 KB Output is correct
17 Correct 54 ms 55580 KB Output is correct
18 Correct 53 ms 55548 KB Output is correct
19 Correct 56 ms 55640 KB Output is correct
20 Correct 53 ms 55544 KB Output is correct
21 Correct 55 ms 55628 KB Output is correct
22 Correct 58 ms 55560 KB Output is correct
23 Correct 55 ms 55596 KB Output is correct
24 Correct 551 ms 94332 KB Output is correct
25 Correct 452 ms 89796 KB Output is correct
26 Correct 510 ms 94480 KB Output is correct
27 Correct 473 ms 92924 KB Output is correct
28 Correct 532 ms 91616 KB Output is correct
29 Correct 332 ms 90448 KB Output is correct
30 Correct 1076 ms 97956 KB Output is correct
31 Correct 287 ms 78284 KB Output is correct
32 Correct 168 ms 69852 KB Output is correct
33 Correct 648 ms 91812 KB Output is correct
34 Correct 863 ms 95572 KB Output is correct
35 Correct 977 ms 91980 KB Output is correct
36 Correct 955 ms 91608 KB Output is correct
37 Correct 542 ms 94476 KB Output is correct
38 Correct 517 ms 95784 KB Output is correct
39 Correct 652 ms 96356 KB Output is correct
40 Correct 663 ms 96356 KB Output is correct
41 Correct 50 ms 55160 KB Output is correct
42 Correct 1087 ms 98052 KB Output is correct
43 Correct 692 ms 94832 KB Output is correct
44 Correct 898 ms 96944 KB Output is correct
45 Correct 1026 ms 95088 KB Output is correct
46 Correct 2725 ms 211752 KB Output is correct
47 Correct 2501 ms 210216 KB Output is correct
48 Correct 3455 ms 223732 KB Output is correct
49 Correct 3610 ms 211768 KB Output is correct
50 Correct 6795 ms 226260 KB Output is correct
51 Correct 3861 ms 194268 KB Output is correct
52 Correct 4873 ms 207248 KB Output is correct
53 Correct 6115 ms 221776 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 98796 KB Output is correct
2 Correct 648 ms 99524 KB Output is correct
3 Correct 369 ms 92636 KB Output is correct
4 Correct 532 ms 92372 KB Output is correct
5 Correct 50 ms 55160 KB Output is correct
6 Correct 588 ms 97472 KB Output is correct
7 Correct 240 ms 78608 KB Output is correct
8 Correct 169 ms 68400 KB Output is correct
9 Correct 376 ms 93632 KB Output is correct
10 Correct 610 ms 92844 KB Output is correct
11 Correct 311 ms 86916 KB Output is correct
12 Correct 49 ms 55160 KB Output is correct
13 Correct 134 ms 55160 KB Output is correct
14 Correct 56 ms 55160 KB Output is correct
15 Correct 55 ms 55212 KB Output is correct
16 Correct 56 ms 55160 KB Output is correct
17 Correct 57 ms 55164 KB Output is correct
18 Correct 57 ms 55160 KB Output is correct
19 Correct 57 ms 55160 KB Output is correct
20 Correct 50 ms 55220 KB Output is correct
21 Correct 51 ms 55160 KB Output is correct
22 Correct 56 ms 55160 KB Output is correct
23 Correct 51 ms 55160 KB Output is correct
24 Correct 56 ms 55160 KB Output is correct
25 Correct 50 ms 55160 KB Output is correct
26 Correct 54 ms 55160 KB Output is correct
27 Correct 52 ms 55316 KB Output is correct
28 Correct 54 ms 55580 KB Output is correct
29 Correct 53 ms 55548 KB Output is correct
30 Correct 56 ms 55640 KB Output is correct
31 Correct 53 ms 55544 KB Output is correct
32 Correct 55 ms 55628 KB Output is correct
33 Correct 58 ms 55560 KB Output is correct
34 Correct 55 ms 55596 KB Output is correct
35 Correct 551 ms 94332 KB Output is correct
36 Correct 452 ms 89796 KB Output is correct
37 Correct 510 ms 94480 KB Output is correct
38 Correct 473 ms 92924 KB Output is correct
39 Correct 532 ms 91616 KB Output is correct
40 Correct 332 ms 90448 KB Output is correct
41 Correct 1076 ms 97956 KB Output is correct
42 Correct 287 ms 78284 KB Output is correct
43 Correct 168 ms 69852 KB Output is correct
44 Correct 648 ms 91812 KB Output is correct
45 Correct 863 ms 95572 KB Output is correct
46 Correct 977 ms 91980 KB Output is correct
47 Correct 955 ms 91608 KB Output is correct
48 Correct 542 ms 94476 KB Output is correct
49 Correct 517 ms 95784 KB Output is correct
50 Correct 652 ms 96356 KB Output is correct
51 Correct 663 ms 96356 KB Output is correct
52 Correct 50 ms 55160 KB Output is correct
53 Correct 1087 ms 98052 KB Output is correct
54 Correct 692 ms 94832 KB Output is correct
55 Correct 898 ms 96944 KB Output is correct
56 Correct 1026 ms 95088 KB Output is correct
57 Correct 537 ms 93268 KB Output is correct
58 Correct 503 ms 92780 KB Output is correct
59 Correct 672 ms 97184 KB Output is correct
60 Correct 667 ms 97432 KB Output is correct
61 Correct 1000 ms 98516 KB Output is correct
62 Correct 50 ms 55160 KB Output is correct
63 Correct 1206 ms 98560 KB Output is correct
64 Correct 683 ms 94604 KB Output is correct
65 Correct 886 ms 98988 KB Output is correct
66 Correct 972 ms 94776 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 98796 KB Output is correct
2 Correct 648 ms 99524 KB Output is correct
3 Correct 369 ms 92636 KB Output is correct
4 Correct 532 ms 92372 KB Output is correct
5 Correct 50 ms 55160 KB Output is correct
6 Correct 588 ms 97472 KB Output is correct
7 Correct 240 ms 78608 KB Output is correct
8 Correct 169 ms 68400 KB Output is correct
9 Correct 376 ms 93632 KB Output is correct
10 Correct 610 ms 92844 KB Output is correct
11 Correct 311 ms 86916 KB Output is correct
12 Correct 49 ms 55160 KB Output is correct
13 Correct 134 ms 55160 KB Output is correct
14 Correct 56 ms 55160 KB Output is correct
15 Correct 55 ms 55212 KB Output is correct
16 Correct 56 ms 55160 KB Output is correct
17 Correct 57 ms 55164 KB Output is correct
18 Correct 57 ms 55160 KB Output is correct
19 Correct 57 ms 55160 KB Output is correct
20 Correct 50 ms 55220 KB Output is correct
21 Correct 51 ms 55160 KB Output is correct
22 Correct 56 ms 55160 KB Output is correct
23 Correct 51 ms 55160 KB Output is correct
24 Correct 56 ms 55160 KB Output is correct
25 Correct 50 ms 55160 KB Output is correct
26 Correct 54 ms 55160 KB Output is correct
27 Correct 52 ms 55316 KB Output is correct
28 Correct 54 ms 55580 KB Output is correct
29 Correct 53 ms 55548 KB Output is correct
30 Correct 56 ms 55640 KB Output is correct
31 Correct 53 ms 55544 KB Output is correct
32 Correct 55 ms 55628 KB Output is correct
33 Correct 58 ms 55560 KB Output is correct
34 Correct 55 ms 55596 KB Output is correct
35 Correct 551 ms 94332 KB Output is correct
36 Correct 452 ms 89796 KB Output is correct
37 Correct 510 ms 94480 KB Output is correct
38 Correct 473 ms 92924 KB Output is correct
39 Correct 532 ms 91616 KB Output is correct
40 Correct 332 ms 90448 KB Output is correct
41 Correct 1076 ms 97956 KB Output is correct
42 Correct 287 ms 78284 KB Output is correct
43 Correct 168 ms 69852 KB Output is correct
44 Correct 648 ms 91812 KB Output is correct
45 Correct 863 ms 95572 KB Output is correct
46 Correct 977 ms 91980 KB Output is correct
47 Correct 955 ms 91608 KB Output is correct
48 Correct 542 ms 94476 KB Output is correct
49 Correct 517 ms 95784 KB Output is correct
50 Correct 652 ms 96356 KB Output is correct
51 Correct 663 ms 96356 KB Output is correct
52 Correct 50 ms 55160 KB Output is correct
53 Correct 1087 ms 98052 KB Output is correct
54 Correct 692 ms 94832 KB Output is correct
55 Correct 898 ms 96944 KB Output is correct
56 Correct 1026 ms 95088 KB Output is correct
57 Correct 2725 ms 211752 KB Output is correct
58 Correct 2501 ms 210216 KB Output is correct
59 Correct 3455 ms 223732 KB Output is correct
60 Correct 3610 ms 211768 KB Output is correct
61 Correct 6795 ms 226260 KB Output is correct
62 Correct 3861 ms 194268 KB Output is correct
63 Correct 4873 ms 207248 KB Output is correct
64 Correct 6115 ms 221776 KB Output is correct
65 Correct 537 ms 93268 KB Output is correct
66 Correct 503 ms 92780 KB Output is correct
67 Correct 672 ms 97184 KB Output is correct
68 Correct 667 ms 97432 KB Output is correct
69 Correct 1000 ms 98516 KB Output is correct
70 Correct 50 ms 55160 KB Output is correct
71 Correct 1206 ms 98560 KB Output is correct
72 Correct 683 ms 94604 KB Output is correct
73 Correct 886 ms 98988 KB Output is correct
74 Correct 972 ms 94776 KB Output is correct
75 Correct 2678 ms 217580 KB Output is correct
76 Correct 2509 ms 198152 KB Output is correct
77 Correct 3568 ms 213892 KB Output is correct
78 Correct 3424 ms 215516 KB Output is correct
79 Correct 6832 ms 240672 KB Output is correct
80 Correct 3788 ms 206452 KB Output is correct
81 Correct 4892 ms 222224 KB Output is correct
82 Correct 6543 ms 223724 KB Output is correct
83 Correct 6138 ms 228020 KB Output is correct