oj.uz

Submission #242843

# Submission time Handle Problem Language Result Execution time Memory
242843 2020-06-29T11:36:56 Z mhy908 Two Dishes (JOI19_dishes) C++14
100 / 100
 5796 ms 293364 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, LL> pil;
const LL llinf=2000000000000000000;

struct LAZY_SEGMENT_TREE{
    struct NODE{
        LL l1, l2, mx;
        NODE(){l2=-llinf;}
    }tree[4000010];
    void propogate(int point, int s, int e){
        tree[point].mx=max(tree[point].mx+tree[point].l1, tree[point].l2);
        if(s!=e){
            tree[point*2].l1+=tree[point].l1;
            tree[point*2+1].l1+=tree[point].l1;
            tree[point*2].l2+=tree[point].l1;
            tree[point*2+1].l2+=tree[point].l1;
            tree[point*2].l2=max(tree[point*2].l2, tree[point].l2);
            tree[point*2+1].l2=max(tree[point*2+1].l2, tree[point].l2);
        }
        tree[point].l1=0;
        tree[point].l2=-llinf;
    }
    LL query(int point, int s, int e, int a){
        propogate(point, s, e);
        if(s==e)return tree[point].mx;
        if(a<=(s+e)/2)return query(point*2, s, (s+e)/2, a);
        return query(point*2+1, (s+e)/2+1, e, a);
    }
    void alter(int point, int s, int e, int a, int b, LL val){
        propogate(point, s, e);
        if(e<a||s>b)return;
        if(a<=s&&e<=b){
            tree[point].l1+=val;
            tree[point].l2+=val;
            //propogate(point, s, e);
            return;
        }
        alter(point*2, s, (s+e)/2, a, b, val);
        alter(point*2+1, (s+e)/2+1, e, a, b, val);
    }
    void update(int point, int s, int e, int a, int b, LL val){
        propogate(point, s, e);
        if(e<a||s>b)return;
        if(a<=s&&e<=b){
            tree[point].l2=max(tree[point].l2, val);
            //propogate(point, s, e);
            return;
        }
        update(point*2, s, (s+e)/2, a, b, val);
        update(point*2+1, (s+e)/2+1, e, a, b, val);
    }
}seg;

int n, m;
LL suma[1000010], sumb[1000010];
LL lima[1000010], limb[1000010];
LL sca[1000010], scb[1000010], ans;
vector<pil> qu[1000010];

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld %lld", &suma[i], &lima[i], &sca[i]);
        suma[i]+=suma[i-1];
    }
    for(int i=1; i<=m; i++){
        scanf("%lld %lld %lld", &sumb[i], &limb[i], &scb[i]);
        sumb[i]+=sumb[i-1];
    }
    for(int i=1; i<=n; i++){
        int tmp=upper_bound(sumb, sumb+m+1, lima[i]-suma[i])-sumb-1;
        if(tmp>=0)qu[i].eb(tmp, sca[i]);
    }
    for(int i=1; i<=m; i++){
        int tmp=upper_bound(suma, suma+n+1, limb[i]-sumb[i])-suma-1;
        if(tmp>=0){
            qu[tmp+1].eb(i-1, -scb[i]);
            ans+=scb[i];
        }
    }
    qu[n+1].eb(m-1, -llinf);
    for(int i=1; i<=n+1; i++){
        svec(qu[i]);
        for(auto j:qu[i])seg.alter(1, 0, m, 0, j.F, j.S);
        for(auto j:qu[i]){
            LL tmp=seg.query(1, 0, m, j.F);
            seg.update(1, 0, m, j.F+1, m, tmp);
        }
    }
    printf("%lld", ans+seg.query(1, 0, m, m));
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:68: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:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &suma[i], &lima[i], &sca[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &sumb[i], &limb[i], &scb[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 150840 KB Output is correct
2 Correct 597 ms 151540 KB Output is correct
3 Correct 469 ms 151144 KB Output is correct
4 Correct 483 ms 146808 KB Output is correct
5 Correct 58 ms 117752 KB Output is correct
6 Correct 554 ms 150512 KB Output is correct
7 Correct 306 ms 133712 KB Output is correct
8 Correct 175 ms 135800 KB Output is correct
9 Correct 481 ms 152300 KB Output is correct
10 Correct 542 ms 144120 KB Output is correct
11 Correct 411 ms 145640 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117752 KB Output is correct
2 Correct 58 ms 117752 KB Output is correct
3 Correct 61 ms 117752 KB Output is correct
4 Correct 56 ms 117752 KB Output is correct
5 Correct 57 ms 117736 KB Output is correct
6 Correct 56 ms 117788 KB Output is correct
7 Correct 56 ms 117752 KB Output is correct
8 Correct 56 ms 117772 KB Output is correct
9 Correct 57 ms 117752 KB Output is correct
10 Correct 55 ms 117752 KB Output is correct
11 Correct 59 ms 117752 KB Output is correct
12 Correct 60 ms 117752 KB Output is correct
13 Correct 56 ms 117752 KB Output is correct
14 Correct 56 ms 117752 KB Output is correct
15 Correct 55 ms 117752 KB Output is correct
16 Correct 57 ms 117756 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117752 KB Output is correct
2 Correct 58 ms 117752 KB Output is correct
3 Correct 61 ms 117752 KB Output is correct
4 Correct 56 ms 117752 KB Output is correct
5 Correct 57 ms 117736 KB Output is correct
6 Correct 56 ms 117788 KB Output is correct
7 Correct 56 ms 117752 KB Output is correct
8 Correct 56 ms 117772 KB Output is correct
9 Correct 57 ms 117752 KB Output is correct
10 Correct 55 ms 117752 KB Output is correct
11 Correct 59 ms 117752 KB Output is correct
12 Correct 60 ms 117752 KB Output is correct
13 Correct 56 ms 117752 KB Output is correct
14 Correct 56 ms 117752 KB Output is correct
15 Correct 55 ms 117752 KB Output is correct
16 Correct 57 ms 117756 KB Output is correct
17 Correct 63 ms 118008 KB Output is correct
18 Correct 61 ms 118136 KB Output is correct
19 Correct 62 ms 118136 KB Output is correct
20 Correct 70 ms 118008 KB Output is correct
21 Correct 67 ms 118136 KB Output is correct
22 Correct 59 ms 118008 KB Output is correct
23 Correct 60 ms 118008 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117752 KB Output is correct
2 Correct 58 ms 117752 KB Output is correct
3 Correct 61 ms 117752 KB Output is correct
4 Correct 56 ms 117752 KB Output is correct
5 Correct 57 ms 117736 KB Output is correct
6 Correct 56 ms 117788 KB Output is correct
7 Correct 56 ms 117752 KB Output is correct
8 Correct 56 ms 117772 KB Output is correct
9 Correct 57 ms 117752 KB Output is correct
10 Correct 55 ms 117752 KB Output is correct
11 Correct 59 ms 117752 KB Output is correct
12 Correct 60 ms 117752 KB Output is correct
13 Correct 56 ms 117752 KB Output is correct
14 Correct 56 ms 117752 KB Output is correct
15 Correct 55 ms 117752 KB Output is correct
16 Correct 57 ms 117756 KB Output is correct
17 Correct 63 ms 118008 KB Output is correct
18 Correct 61 ms 118136 KB Output is correct
19 Correct 62 ms 118136 KB Output is correct
20 Correct 70 ms 118008 KB Output is correct
21 Correct 67 ms 118136 KB Output is correct
22 Correct 59 ms 118008 KB Output is correct
23 Correct 60 ms 118008 KB Output is correct
24 Correct 520 ms 146312 KB Output is correct
25 Correct 448 ms 145260 KB Output is correct
26 Correct 523 ms 146328 KB Output is correct
27 Correct 469 ms 145784 KB Output is correct
28 Correct 556 ms 147292 KB Output is correct
29 Correct 453 ms 149120 KB Output is correct
30 Correct 852 ms 149452 KB Output is correct
31 Correct 308 ms 131044 KB Output is correct
32 Correct 174 ms 134112 KB Output is correct
33 Correct 617 ms 143100 KB Output is correct
34 Correct 762 ms 148684 KB Output is correct
35 Correct 809 ms 143332 KB Output is correct
36 Correct 797 ms 143224 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117752 KB Output is correct
2 Correct 58 ms 117752 KB Output is correct
3 Correct 61 ms 117752 KB Output is correct
4 Correct 56 ms 117752 KB Output is correct
5 Correct 57 ms 117736 KB Output is correct
6 Correct 56 ms 117788 KB Output is correct
7 Correct 56 ms 117752 KB Output is correct
8 Correct 56 ms 117772 KB Output is correct
9 Correct 57 ms 117752 KB Output is correct
10 Correct 55 ms 117752 KB Output is correct
11 Correct 59 ms 117752 KB Output is correct
12 Correct 60 ms 117752 KB Output is correct
13 Correct 56 ms 117752 KB Output is correct
14 Correct 56 ms 117752 KB Output is correct
15 Correct 55 ms 117752 KB Output is correct
16 Correct 57 ms 117756 KB Output is correct
17 Correct 63 ms 118008 KB Output is correct
18 Correct 61 ms 118136 KB Output is correct
19 Correct 62 ms 118136 KB Output is correct
20 Correct 70 ms 118008 KB Output is correct
21 Correct 67 ms 118136 KB Output is correct
22 Correct 59 ms 118008 KB Output is correct
23 Correct 60 ms 118008 KB Output is correct
24 Correct 520 ms 146312 KB Output is correct
25 Correct 448 ms 145260 KB Output is correct
26 Correct 523 ms 146328 KB Output is correct
27 Correct 469 ms 145784 KB Output is correct
28 Correct 556 ms 147292 KB Output is correct
29 Correct 453 ms 149120 KB Output is correct
30 Correct 852 ms 149452 KB Output is correct
31 Correct 308 ms 131044 KB Output is correct
32 Correct 174 ms 134112 KB Output is correct
33 Correct 617 ms 143100 KB Output is correct
34 Correct 762 ms 148684 KB Output is correct
35 Correct 809 ms 143332 KB Output is correct
36 Correct 797 ms 143224 KB Output is correct
37 Correct 554 ms 149356 KB Output is correct
38 Correct 490 ms 148728 KB Output is correct
39 Correct 602 ms 147788 KB Output is correct
40 Correct 620 ms 147832 KB Output is correct
41 Correct 67 ms 117756 KB Output is correct
42 Correct 917 ms 152696 KB Output is correct
43 Correct 595 ms 146168 KB Output is correct
44 Correct 804 ms 151544 KB Output is correct
45 Correct 801 ms 146424 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 117752 KB Output is correct
2 Correct 58 ms 117752 KB Output is correct
3 Correct 61 ms 117752 KB Output is correct
4 Correct 56 ms 117752 KB Output is correct
5 Correct 57 ms 117736 KB Output is correct
6 Correct 56 ms 117788 KB Output is correct
7 Correct 56 ms 117752 KB Output is correct
8 Correct 56 ms 117772 KB Output is correct
9 Correct 57 ms 117752 KB Output is correct
10 Correct 55 ms 117752 KB Output is correct
11 Correct 59 ms 117752 KB Output is correct
12 Correct 60 ms 117752 KB Output is correct
13 Correct 56 ms 117752 KB Output is correct
14 Correct 56 ms 117752 KB Output is correct
15 Correct 55 ms 117752 KB Output is correct
16 Correct 57 ms 117756 KB Output is correct
17 Correct 63 ms 118008 KB Output is correct
18 Correct 61 ms 118136 KB Output is correct
19 Correct 62 ms 118136 KB Output is correct
20 Correct 70 ms 118008 KB Output is correct
21 Correct 67 ms 118136 KB Output is correct
22 Correct 59 ms 118008 KB Output is correct
23 Correct 60 ms 118008 KB Output is correct
24 Correct 520 ms 146312 KB Output is correct
25 Correct 448 ms 145260 KB Output is correct
26 Correct 523 ms 146328 KB Output is correct
27 Correct 469 ms 145784 KB Output is correct
28 Correct 556 ms 147292 KB Output is correct
29 Correct 453 ms 149120 KB Output is correct
30 Correct 852 ms 149452 KB Output is correct
31 Correct 308 ms 131044 KB Output is correct
32 Correct 174 ms 134112 KB Output is correct
33 Correct 617 ms 143100 KB Output is correct
34 Correct 762 ms 148684 KB Output is correct
35 Correct 809 ms 143332 KB Output is correct
36 Correct 797 ms 143224 KB Output is correct
37 Correct 554 ms 149356 KB Output is correct
38 Correct 490 ms 148728 KB Output is correct
39 Correct 602 ms 147788 KB Output is correct
40 Correct 620 ms 147832 KB Output is correct
41 Correct 67 ms 117756 KB Output is correct
42 Correct 917 ms 152696 KB Output is correct
43 Correct 595 ms 146168 KB Output is correct
44 Correct 804 ms 151544 KB Output is correct
45 Correct 801 ms 146424 KB Output is correct
46 Correct 2704 ms 274268 KB Output is correct
47 Correct 2498 ms 273996 KB Output is correct
48 Correct 3018 ms 268240 KB Output is correct
49 Correct 3002 ms 268072 KB Output is correct
50 Correct 5560 ms 293364 KB Output is correct
51 Correct 3144 ms 257612 KB Output is correct
52 Correct 4075 ms 281268 KB Output is correct
53 Correct 4969 ms 260832 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 150840 KB Output is correct
2 Correct 597 ms 151540 KB Output is correct
3 Correct 469 ms 151144 KB Output is correct
4 Correct 483 ms 146808 KB Output is correct
5 Correct 58 ms 117752 KB Output is correct
6 Correct 554 ms 150512 KB Output is correct
7 Correct 306 ms 133712 KB Output is correct
8 Correct 175 ms 135800 KB Output is correct
9 Correct 481 ms 152300 KB Output is correct
10 Correct 542 ms 144120 KB Output is correct
11 Correct 411 ms 145640 KB Output is correct
12 Correct 58 ms 117752 KB Output is correct
13 Correct 58 ms 117752 KB Output is correct
14 Correct 61 ms 117752 KB Output is correct
15 Correct 56 ms 117752 KB Output is correct
16 Correct 57 ms 117736 KB Output is correct
17 Correct 56 ms 117788 KB Output is correct
18 Correct 56 ms 117752 KB Output is correct
19 Correct 56 ms 117772 KB Output is correct
20 Correct 57 ms 117752 KB Output is correct
21 Correct 55 ms 117752 KB Output is correct
22 Correct 59 ms 117752 KB Output is correct
23 Correct 60 ms 117752 KB Output is correct
24 Correct 56 ms 117752 KB Output is correct
25 Correct 56 ms 117752 KB Output is correct
26 Correct 55 ms 117752 KB Output is correct
27 Correct 57 ms 117756 KB Output is correct
28 Correct 63 ms 118008 KB Output is correct
29 Correct 61 ms 118136 KB Output is correct
30 Correct 62 ms 118136 KB Output is correct
31 Correct 70 ms 118008 KB Output is correct
32 Correct 67 ms 118136 KB Output is correct
33 Correct 59 ms 118008 KB Output is correct
34 Correct 60 ms 118008 KB Output is correct
35 Correct 520 ms 146312 KB Output is correct
36 Correct 448 ms 145260 KB Output is correct
37 Correct 523 ms 146328 KB Output is correct
38 Correct 469 ms 145784 KB Output is correct
39 Correct 556 ms 147292 KB Output is correct
40 Correct 453 ms 149120 KB Output is correct
41 Correct 852 ms 149452 KB Output is correct
42 Correct 308 ms 131044 KB Output is correct
43 Correct 174 ms 134112 KB Output is correct
44 Correct 617 ms 143100 KB Output is correct
45 Correct 762 ms 148684 KB Output is correct
46 Correct 809 ms 143332 KB Output is correct
47 Correct 797 ms 143224 KB Output is correct
48 Correct 554 ms 149356 KB Output is correct
49 Correct 490 ms 148728 KB Output is correct
50 Correct 602 ms 147788 KB Output is correct
51 Correct 620 ms 147832 KB Output is correct
52 Correct 67 ms 117756 KB Output is correct
53 Correct 917 ms 152696 KB Output is correct
54 Correct 595 ms 146168 KB Output is correct
55 Correct 804 ms 151544 KB Output is correct
56 Correct 801 ms 146424 KB Output is correct
57 Correct 566 ms 149900 KB Output is correct
58 Correct 509 ms 149112 KB Output is correct
59 Correct 640 ms 148728 KB Output is correct
60 Correct 648 ms 148600 KB Output is correct
61 Correct 879 ms 149880 KB Output is correct
62 Correct 64 ms 117856 KB Output is correct
63 Correct 940 ms 152924 KB Output is correct
64 Correct 675 ms 146100 KB Output is correct
65 Correct 754 ms 151268 KB Output is correct
66 Correct 801 ms 146328 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 150840 KB Output is correct
2 Correct 597 ms 151540 KB Output is correct
3 Correct 469 ms 151144 KB Output is correct
4 Correct 483 ms 146808 KB Output is correct
5 Correct 58 ms 117752 KB Output is correct
6 Correct 554 ms 150512 KB Output is correct
7 Correct 306 ms 133712 KB Output is correct
8 Correct 175 ms 135800 KB Output is correct
9 Correct 481 ms 152300 KB Output is correct
10 Correct 542 ms 144120 KB Output is correct
11 Correct 411 ms 145640 KB Output is correct
12 Correct 58 ms 117752 KB Output is correct
13 Correct 58 ms 117752 KB Output is correct
14 Correct 61 ms 117752 KB Output is correct
15 Correct 56 ms 117752 KB Output is correct
16 Correct 57 ms 117736 KB Output is correct
17 Correct 56 ms 117788 KB Output is correct
18 Correct 56 ms 117752 KB Output is correct
19 Correct 56 ms 117772 KB Output is correct
20 Correct 57 ms 117752 KB Output is correct
21 Correct 55 ms 117752 KB Output is correct
22 Correct 59 ms 117752 KB Output is correct
23 Correct 60 ms 117752 KB Output is correct
24 Correct 56 ms 117752 KB Output is correct
25 Correct 56 ms 117752 KB Output is correct
26 Correct 55 ms 117752 KB Output is correct
27 Correct 57 ms 117756 KB Output is correct
28 Correct 63 ms 118008 KB Output is correct
29 Correct 61 ms 118136 KB Output is correct
30 Correct 62 ms 118136 KB Output is correct
31 Correct 70 ms 118008 KB Output is correct
32 Correct 67 ms 118136 KB Output is correct
33 Correct 59 ms 118008 KB Output is correct
34 Correct 60 ms 118008 KB Output is correct
35 Correct 520 ms 146312 KB Output is correct
36 Correct 448 ms 145260 KB Output is correct
37 Correct 523 ms 146328 KB Output is correct
38 Correct 469 ms 145784 KB Output is correct
39 Correct 556 ms 147292 KB Output is correct
40 Correct 453 ms 149120 KB Output is correct
41 Correct 852 ms 149452 KB Output is correct
42 Correct 308 ms 131044 KB Output is correct
43 Correct 174 ms 134112 KB Output is correct
44 Correct 617 ms 143100 KB Output is correct
45 Correct 762 ms 148684 KB Output is correct
46 Correct 809 ms 143332 KB Output is correct
47 Correct 797 ms 143224 KB Output is correct
48 Correct 554 ms 149356 KB Output is correct
49 Correct 490 ms 148728 KB Output is correct
50 Correct 602 ms 147788 KB Output is correct
51 Correct 620 ms 147832 KB Output is correct
52 Correct 67 ms 117756 KB Output is correct
53 Correct 917 ms 152696 KB Output is correct
54 Correct 595 ms 146168 KB Output is correct
55 Correct 804 ms 151544 KB Output is correct
56 Correct 801 ms 146424 KB Output is correct
57 Correct 2704 ms 274268 KB Output is correct
58 Correct 2498 ms 273996 KB Output is correct
59 Correct 3018 ms 268240 KB Output is correct
60 Correct 3002 ms 268072 KB Output is correct
61 Correct 5560 ms 293364 KB Output is correct
62 Correct 3144 ms 257612 KB Output is correct
63 Correct 4075 ms 281268 KB Output is correct
64 Correct 4969 ms 260832 KB Output is correct
65 Correct 566 ms 149900 KB Output is correct
66 Correct 509 ms 149112 KB Output is correct
67 Correct 640 ms 148728 KB Output is correct
68 Correct 648 ms 148600 KB Output is correct
69 Correct 879 ms 149880 KB Output is correct
70 Correct 64 ms 117856 KB Output is correct
71 Correct 940 ms 152924 KB Output is correct
72 Correct 675 ms 146100 KB Output is correct
73 Correct 754 ms 151268 KB Output is correct
74 Correct 801 ms 146328 KB Output is correct
75 Correct 2732 ms 275956 KB Output is correct
76 Correct 2423 ms 274936 KB Output is correct
77 Correct 3071 ms 268560 KB Output is correct
78 Correct 3075 ms 268916 KB Output is correct
79 Correct 5796 ms 290896 KB Output is correct
80 Correct 3218 ms 257016 KB Output is correct
81 Correct 4499 ms 277364 KB Output is correct
82 Correct 5175 ms 260372 KB Output is correct
83 Correct 5127 ms 278444 KB Output is correct