oj.uz

Submission #1069888

# Submission time Handle Problem Language Result Execution time Memory
1069888 2024-08-22T09:38:38 Z heeew Two Dishes (JOI19_dishes) C++14
74 / 100
 2977 ms 246256 KB 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_N=1000010;
const lint INF=2.1e+15;

struct Seg
{
    lint sum;
    lint v,lazy;
    void setv(lint vp,lint lp)
    {
        v=max(v+lp,vp);
        lazy+=lp;
    }
};


int n,m;
lint t1[MAX_N],t2[MAX_N],c1[MAX_N],c2[MAX_N],s1[MAX_N],s2[MAX_N];
lint ts1[MAX_N],ts2[MAX_N],ci[MAX_N];
Seg seg[MAX_N<<2];
vint endp[MAX_N];

void update_lazy(int i)
{
    seg[i<<1].sum+=seg[i].sum;
    seg[i<<1|1].sum+=seg[i].sum;
    seg[i<<1].setv(seg[i].v,seg[i].lazy);
    seg[i<<1|1].setv(seg[i].v,seg[i].lazy);
    seg[i].sum=0;
    seg[i].v=min(seg[i<<1].v,seg[i<<1|1].v);
    seg[i].lazy=0;
}

void update_sum(int i,int s,int e,int l,int r,lint v)
{
    if(s>=r || e<=l)return;
    if(l<=s && e<=r)
    {
        seg[i].sum+=v;
        return;
    }
    update_lazy(i);
    update_sum(i<<1,s,(s+e)>>1,l,r,v);
    update_sum(i<<1|1,(s+e)>>1,e,l,r,v);
}

void update_(int i,int s,int e,int l,int r,lint add,lint cut)
{
    if(s>=r || e<=l)return;
    if(l<=s && e<=r)
    {
        seg[i].setv(cut,add);
        return;
    }
    update_lazy(i);
    update_(i<<1,s,(s+e)>>1,l,r,add,cut);
    update_(i<<1|1,(s+e)>>1,e,l,r,add,cut);
}

lint find_(int i,int s,int e,int x,int t)
{
    if(s>x || e<=x)return 0;
    if(s==x && x+1==e)return seg[i].v+seg[i].sum*t;
    update_lazy(i);
    return find_(i<<1,s,(s+e)>>1,x,t)+find_(i<<1|1,(s+e)>>1,e,x,t);
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        cin >> t1[i] >> c1[i] >> s1[i];
        ts1[i]=t1[i]+ts1[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        cin >> t2[i] >> c2[i] >> s2[i];
        ts2[i]=t2[i]+ts2[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        int p=upper_bound(ts2,ts2+m+1,c1[i]-ts1[i])-ts2;
        if(!p)continue;
        endp[p].push_back(i);
        update_sum(1,0,n+1,i,n+1,s1[i]);
    }
    for(int i=1;i<=m;i++)
        ci[i]=upper_bound(ts1,ts1+n+1,c2[i]-ts2[i])-ts1;
    for(int i=1;i<=m;i++)
    {
        vint cutted;
        lint cut=-INF;
        update_(1,0,n+1,0,ci[i],s2[i],cut);
        cutted.push_back(ci[i]);
        for(auto j : endp[i])
        {
            update_sum(1,0,n+1,j,n+1,-s1[j]);
            update_(1,0,n+1,j,n+1,s1[j],cut);
            cutted.push_back(j);
        }
        sort(cutted.begin(),cutted.end());
        for(auto p : cutted)
        {
            if(!p)continue;
            cut=find_(1,0,n+1,p-1,0);
            update_(1,0,n+1,p,n+1,0,cut);
        }
        cutted.clear();
    }
    cout << find_(1,0,n+1,n,1);
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 68436 KB Output is correct
2 Correct 335 ms 68532 KB Output is correct
3 Correct 190 ms 78856 KB Output is correct
4 Correct 275 ms 82336 KB Output is correct
5 Correct 6 ms 39512 KB Output is correct
6 Correct 292 ms 81296 KB Output is correct
7 Correct 59 ms 52560 KB Output is correct
8 Correct 74 ms 66228 KB Output is correct
9 Correct 164 ms 80076 KB Output is correct
10 Correct 313 ms 78416 KB Output is correct
11 Correct 135 ms 73420 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39512 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39516 KB Output is correct
5 Correct 5 ms 39516 KB Output is correct
6 Correct 5 ms 39516 KB Output is correct
7 Correct 5 ms 39516 KB Output is correct
8 Correct 5 ms 39512 KB Output is correct
9 Correct 5 ms 39516 KB Output is correct
10 Correct 5 ms 39592 KB Output is correct
11 Correct 5 ms 39520 KB Output is correct
12 Correct 5 ms 39516 KB Output is correct
13 Correct 5 ms 39516 KB Output is correct
14 Correct 6 ms 39516 KB Output is correct
15 Correct 6 ms 39536 KB Output is correct
16 Correct 6 ms 39512 KB Output is correct
17 Correct 7 ms 39772 KB Output is correct
18 Correct 7 ms 39768 KB Output is correct
19 Correct 9 ms 39772 KB Output is correct
20 Correct 7 ms 39772 KB Output is correct
21 Correct 9 ms 39772 KB Output is correct
22 Correct 9 ms 39516 KB Output is correct
23 Correct 8 ms 39516 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39512 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39516 KB Output is correct
5 Correct 5 ms 39516 KB Output is correct
6 Correct 5 ms 39516 KB Output is correct
7 Correct 5 ms 39516 KB Output is correct
8 Correct 5 ms 39512 KB Output is correct
9 Correct 5 ms 39516 KB Output is correct
10 Correct 5 ms 39592 KB Output is correct
11 Correct 5 ms 39520 KB Output is correct
12 Correct 5 ms 39516 KB Output is correct
13 Correct 5 ms 39516 KB Output is correct
14 Correct 6 ms 39516 KB Output is correct
15 Correct 6 ms 39536 KB Output is correct
16 Correct 6 ms 39512 KB Output is correct
17 Correct 7 ms 39772 KB Output is correct
18 Correct 7 ms 39768 KB Output is correct
19 Correct 9 ms 39772 KB Output is correct
20 Correct 7 ms 39772 KB Output is correct
21 Correct 9 ms 39772 KB Output is correct
22 Correct 9 ms 39516 KB Output is correct
23 Correct 8 ms 39516 KB Output is correct
24 Correct 262 ms 77688 KB Output is correct
25 Correct 213 ms 75728 KB Output is correct
26 Correct 286 ms 81704 KB Output is correct
27 Correct 209 ms 75984 KB Output is correct
28 Correct 228 ms 77260 KB Output is correct
29 Correct 173 ms 77004 KB Output is correct
30 Correct 539 ms 79380 KB Output is correct
31 Correct 56 ms 51028 KB Output is correct
32 Correct 130 ms 65224 KB Output is correct
33 Correct 280 ms 77632 KB Output is correct
34 Correct 392 ms 77776 KB Output is correct
35 Correct 459 ms 72788 KB Output is correct
36 Correct 423 ms 72788 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39512 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39516 KB Output is correct
5 Correct 5 ms 39516 KB Output is correct
6 Correct 5 ms 39516 KB Output is correct
7 Correct 5 ms 39516 KB Output is correct
8 Correct 5 ms 39512 KB Output is correct
9 Correct 5 ms 39516 KB Output is correct
10 Correct 5 ms 39592 KB Output is correct
11 Correct 5 ms 39520 KB Output is correct
12 Correct 5 ms 39516 KB Output is correct
13 Correct 5 ms 39516 KB Output is correct
14 Correct 6 ms 39516 KB Output is correct
15 Correct 6 ms 39536 KB Output is correct
16 Correct 6 ms 39512 KB Output is correct
17 Correct 7 ms 39772 KB Output is correct
18 Correct 7 ms 39768 KB Output is correct
19 Correct 9 ms 39772 KB Output is correct
20 Correct 7 ms 39772 KB Output is correct
21 Correct 9 ms 39772 KB Output is correct
22 Correct 9 ms 39516 KB Output is correct
23 Correct 8 ms 39516 KB Output is correct
24 Correct 262 ms 77688 KB Output is correct
25 Correct 213 ms 75728 KB Output is correct
26 Correct 286 ms 81704 KB Output is correct
27 Correct 209 ms 75984 KB Output is correct
28 Correct 228 ms 77260 KB Output is correct
29 Correct 173 ms 77004 KB Output is correct
30 Correct 539 ms 79380 KB Output is correct
31 Correct 56 ms 51028 KB Output is correct
32 Correct 130 ms 65224 KB Output is correct
33 Correct 280 ms 77632 KB Output is correct
34 Correct 392 ms 77776 KB Output is correct
35 Correct 459 ms 72788 KB Output is correct
36 Correct 423 ms 72788 KB Output is correct
37 Correct 284 ms 84560 KB Output is correct
38 Correct 214 ms 78796 KB Output is correct
39 Correct 348 ms 82000 KB Output is correct
40 Correct 337 ms 82328 KB Output is correct
41 Correct 6 ms 39516 KB Output is correct
42 Correct 485 ms 82320 KB Output is correct
43 Correct 300 ms 80464 KB Output is correct
44 Correct 402 ms 80848 KB Output is correct
45 Correct 440 ms 76096 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39512 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Correct 5 ms 39516 KB Output is correct
4 Correct 5 ms 39516 KB Output is correct
5 Correct 5 ms 39516 KB Output is correct
6 Correct 5 ms 39516 KB Output is correct
7 Correct 5 ms 39516 KB Output is correct
8 Correct 5 ms 39512 KB Output is correct
9 Correct 5 ms 39516 KB Output is correct
10 Correct 5 ms 39592 KB Output is correct
11 Correct 5 ms 39520 KB Output is correct
12 Correct 5 ms 39516 KB Output is correct
13 Correct 5 ms 39516 KB Output is correct
14 Correct 6 ms 39516 KB Output is correct
15 Correct 6 ms 39536 KB Output is correct
16 Correct 6 ms 39512 KB Output is correct
17 Correct 7 ms 39772 KB Output is correct
18 Correct 7 ms 39768 KB Output is correct
19 Correct 9 ms 39772 KB Output is correct
20 Correct 7 ms 39772 KB Output is correct
21 Correct 9 ms 39772 KB Output is correct
22 Correct 9 ms 39516 KB Output is correct
23 Correct 8 ms 39516 KB Output is correct
24 Correct 262 ms 77688 KB Output is correct
25 Correct 213 ms 75728 KB Output is correct
26 Correct 286 ms 81704 KB Output is correct
27 Correct 209 ms 75984 KB Output is correct
28 Correct 228 ms 77260 KB Output is correct
29 Correct 173 ms 77004 KB Output is correct
30 Correct 539 ms 79380 KB Output is correct
31 Correct 56 ms 51028 KB Output is correct
32 Correct 130 ms 65224 KB Output is correct
33 Correct 280 ms 77632 KB Output is correct
34 Correct 392 ms 77776 KB Output is correct
35 Correct 459 ms 72788 KB Output is correct
36 Correct 423 ms 72788 KB Output is correct
37 Correct 284 ms 84560 KB Output is correct
38 Correct 214 ms 78796 KB Output is correct
39 Correct 348 ms 82000 KB Output is correct
40 Correct 337 ms 82328 KB Output is correct
41 Correct 6 ms 39516 KB Output is correct
42 Correct 485 ms 82320 KB Output is correct
43 Correct 300 ms 80464 KB Output is correct
44 Correct 402 ms 80848 KB Output is correct
45 Correct 440 ms 76096 KB Output is correct
46 Correct 1490 ms 246256 KB Output is correct
47 Correct 1132 ms 217040 KB Output is correct
48 Correct 1804 ms 232732 KB Output is correct
49 Correct 1793 ms 232788 KB Output is correct
50 Correct 2977 ms 235088 KB Output is correct
51 Correct 1631 ms 223360 KB Output is correct
52 Correct 2081 ms 220684 KB Output is correct
53 Correct 2723 ms 203280 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 68436 KB Output is correct
2 Correct 335 ms 68532 KB Output is correct
3 Correct 190 ms 78856 KB Output is correct
4 Correct 275 ms 82336 KB Output is correct
5 Correct 6 ms 39512 KB Output is correct
6 Correct 292 ms 81296 KB Output is correct
7 Correct 59 ms 52560 KB Output is correct
8 Correct 74 ms 66228 KB Output is correct
9 Correct 164 ms 80076 KB Output is correct
10 Correct 313 ms 78416 KB Output is correct
11 Correct 135 ms 73420 KB Output is correct
12 Correct 5 ms 39512 KB Output is correct
13 Correct 5 ms 39516 KB Output is correct
14 Correct 5 ms 39516 KB Output is correct
15 Correct 5 ms 39516 KB Output is correct
16 Correct 5 ms 39516 KB Output is correct
17 Correct 5 ms 39516 KB Output is correct
18 Correct 5 ms 39516 KB Output is correct
19 Correct 5 ms 39512 KB Output is correct
20 Correct 5 ms 39516 KB Output is correct
21 Correct 5 ms 39592 KB Output is correct
22 Correct 5 ms 39520 KB Output is correct
23 Correct 5 ms 39516 KB Output is correct
24 Correct 5 ms 39516 KB Output is correct
25 Correct 6 ms 39516 KB Output is correct
26 Correct 6 ms 39536 KB Output is correct
27 Correct 6 ms 39512 KB Output is correct
28 Correct 7 ms 39772 KB Output is correct
29 Correct 7 ms 39768 KB Output is correct
30 Correct 9 ms 39772 KB Output is correct
31 Correct 7 ms 39772 KB Output is correct
32 Correct 9 ms 39772 KB Output is correct
33 Correct 9 ms 39516 KB Output is correct
34 Correct 8 ms 39516 KB Output is correct
35 Correct 262 ms 77688 KB Output is correct
36 Correct 213 ms 75728 KB Output is correct
37 Correct 286 ms 81704 KB Output is correct
38 Correct 209 ms 75984 KB Output is correct
39 Correct 228 ms 77260 KB Output is correct
40 Correct 173 ms 77004 KB Output is correct
41 Correct 539 ms 79380 KB Output is correct
42 Correct 56 ms 51028 KB Output is correct
43 Correct 130 ms 65224 KB Output is correct
44 Correct 280 ms 77632 KB Output is correct
45 Correct 392 ms 77776 KB Output is correct
46 Correct 459 ms 72788 KB Output is correct
47 Correct 423 ms 72788 KB Output is correct
48 Correct 284 ms 84560 KB Output is correct
49 Correct 214 ms 78796 KB Output is correct
50 Correct 348 ms 82000 KB Output is correct
51 Correct 337 ms 82328 KB Output is correct
52 Correct 6 ms 39516 KB Output is correct
53 Correct 485 ms 82320 KB Output is correct
54 Correct 300 ms 80464 KB Output is correct
55 Correct 402 ms 80848 KB Output is correct
56 Correct 440 ms 76096 KB Output is correct
57 Correct 274 ms 85068 KB Output is correct
58 Correct 222 ms 79524 KB Output is correct
59 Incorrect 347 ms 83028 KB Output isn't correct
60 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 68436 KB Output is correct
2 Correct 335 ms 68532 KB Output is correct
3 Correct 190 ms 78856 KB Output is correct
4 Correct 275 ms 82336 KB Output is correct
5 Correct 6 ms 39512 KB Output is correct
6 Correct 292 ms 81296 KB Output is correct
7 Correct 59 ms 52560 KB Output is correct
8 Correct 74 ms 66228 KB Output is correct
9 Correct 164 ms 80076 KB Output is correct
10 Correct 313 ms 78416 KB Output is correct
11 Correct 135 ms 73420 KB Output is correct
12 Correct 5 ms 39512 KB Output is correct
13 Correct 5 ms 39516 KB Output is correct
14 Correct 5 ms 39516 KB Output is correct
15 Correct 5 ms 39516 KB Output is correct
16 Correct 5 ms 39516 KB Output is correct
17 Correct 5 ms 39516 KB Output is correct
18 Correct 5 ms 39516 KB Output is correct
19 Correct 5 ms 39512 KB Output is correct
20 Correct 5 ms 39516 KB Output is correct
21 Correct 5 ms 39592 KB Output is correct
22 Correct 5 ms 39520 KB Output is correct
23 Correct 5 ms 39516 KB Output is correct
24 Correct 5 ms 39516 KB Output is correct
25 Correct 6 ms 39516 KB Output is correct
26 Correct 6 ms 39536 KB Output is correct
27 Correct 6 ms 39512 KB Output is correct
28 Correct 7 ms 39772 KB Output is correct
29 Correct 7 ms 39768 KB Output is correct
30 Correct 9 ms 39772 KB Output is correct
31 Correct 7 ms 39772 KB Output is correct
32 Correct 9 ms 39772 KB Output is correct
33 Correct 9 ms 39516 KB Output is correct
34 Correct 8 ms 39516 KB Output is correct
35 Correct 262 ms 77688 KB Output is correct
36 Correct 213 ms 75728 KB Output is correct
37 Correct 286 ms 81704 KB Output is correct
38 Correct 209 ms 75984 KB Output is correct
39 Correct 228 ms 77260 KB Output is correct
40 Correct 173 ms 77004 KB Output is correct
41 Correct 539 ms 79380 KB Output is correct
42 Correct 56 ms 51028 KB Output is correct
43 Correct 130 ms 65224 KB Output is correct
44 Correct 280 ms 77632 KB Output is correct
45 Correct 392 ms 77776 KB Output is correct
46 Correct 459 ms 72788 KB Output is correct
47 Correct 423 ms 72788 KB Output is correct
48 Correct 284 ms 84560 KB Output is correct
49 Correct 214 ms 78796 KB Output is correct
50 Correct 348 ms 82000 KB Output is correct
51 Correct 337 ms 82328 KB Output is correct
52 Correct 6 ms 39516 KB Output is correct
53 Correct 485 ms 82320 KB Output is correct
54 Correct 300 ms 80464 KB Output is correct
55 Correct 402 ms 80848 KB Output is correct
56 Correct 440 ms 76096 KB Output is correct
57 Correct 1490 ms 246256 KB Output is correct
58 Correct 1132 ms 217040 KB Output is correct
59 Correct 1804 ms 232732 KB Output is correct
60 Correct 1793 ms 232788 KB Output is correct
61 Correct 2977 ms 235088 KB Output is correct
62 Correct 1631 ms 223360 KB Output is correct
63 Correct 2081 ms 220684 KB Output is correct
64 Correct 2723 ms 203280 KB Output is correct
65 Correct 274 ms 85068 KB Output is correct
66 Correct 222 ms 79524 KB Output is correct
67 Incorrect 347 ms 83028 KB Output isn't correct
68 Halted 0 ms 0 KB -