oj.uz

Submission #579487

# Submission time Handle Problem Language Result Execution time Memory
579487 2022-06-19T08:53:41 Z Lucpp Two Dishes (JOI19_dishes) C++17
74 / 100
 4962 ms 100104 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAX = 1e6+2;

ll A[2][MAX], T[2][MAX], P[2][MAX];
int B[2][MAX];

struct Seg{
    vector<ll> S, O;
    vector<bool> lazy;
    int cap;
    void init(int n){
        for(cap = 1; cap < n; cap*=2);
        S.assign(2*cap, -INF);
        O.assign(2*cap, 0);
        lazy.assign(2*cap, false);
    }
    void push(int i){
        if(lazy[i]){
            S[2*i] += O[i];
            O[2*i] += O[i];
            lazy[2*i] = true;
            S[2*i+1] += O[i];
            O[2*i+1] += O[i];
            lazy[2*i+1] = true;
            O[i] = 0;
            lazy[i] = false;
        }
    }
    void add(int l, int r, ll v, int a, int b, int i){
        if(l <= a && b <= r){
            S[i] += v;
            O[i] += v;
            lazy[i] = true;
        }
        else if(b < l || r < a);
        else{
            push(i);
            int m = (a+b)/2;
            add(l, r, v, a, m, 2*i);
            add(l, r, v, m+1, b, 2*i+1);
            S[i] = max(S[2*i], S[2*i+1]);
        }
    }
    void add(int l, int r, ll v){add(l, r, v, 1, cap, 1);}
    void upd(int p, ll v, int a, int b, int i){
        if(a == b) S[i] = v;
        else{
            push(i);
            int m = (a+b)/2;
            if(p <= m) upd(p, v, a, m, 2*i);
            else upd(p, v, m+1, b, 2*i+1);
            S[i] = max(S[2*i], S[2*i+1]);
        }
    }
    void upd(int p, ll v){upd(p, v, 1, cap, 1);}
    ll qry(int l, int r, int a, int b, int i){
        if(l <= a && b <= r) return S[i];
        if(b < l || r < a) return -INF;
        push(i);
        int m = (a+b)/2;
        return max(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
    }
    ll qry(int l, int r){return qry(l, r, 1, cap, 1);}
};

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < 2; i++){
        A[i][0] = P[i][0] = 0;
        for(int j = 1; j <= (i==0?n:m); j++){
            cin >> A[i][j] >> T[i][j] >> P[i][j];
            A[i][j] += A[i][j-1];
        }
    }
    
    for(int i = 0; i < 2; i++){
        B[i][0] = 0;
        int x = (i==0?m:n);
        for(int j = 1; j <= (i==0?n:m); j++){
            if(A[i][j] > T[i][j]) B[i][j] = -1;
            else if(A[i][j]+A[1-i][x] <= T[i][j]) B[i][j] = x;
            else B[i][j] = (int)(upper_bound(A[1-i], A[1-i]+x, T[i][j]-A[i][j])-A[1-i]-1);
        }
    }
    n++;
    B[0][n] = m;
    P[0][n] = 0;
    n++;

    vector<pair<int, int>> byH;
    for(int i = 1; i < n; i++) if(B[0][i] >= 0) byH.emplace_back(B[0][i], i);
    sort(byH.begin(), byH.end());

    ll sum = 0;
    for(int i = 0; i < n; ++i){
        if(B[0][i] >= 0) sum += P[0][i];
    }
    Seg seg; seg.init(n);
    seg.upd(1, sum);

    vector<int> todo;
    int lastH = 0;
    for(auto [h, i] : byH){
        if(lastH != h){
            for(int j : todo){
                seg.add(1, j, -P[0][j]);
            }
            todo.clear();
            for(int j = lastH+1; j <= h; j++){
                if(B[1][j] >= 0){
                    seg.add(1, B[1][j]+1, P[1][j]);
                }
            }
        }
        ll dp = seg.qry(1, i);
        seg.upd(i+1, dp);
        lastH = h;
        todo.push_back(i);
    }
    ll ans = seg.qry(n, n);
    cout << ans << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 21844 KB Output is correct
2 Correct 677 ms 21840 KB Output is correct
3 Correct 612 ms 23332 KB Output is correct
4 Correct 603 ms 20800 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 641 ms 21480 KB Output is correct
7 Correct 244 ms 6296 KB Output is correct
8 Correct 329 ms 17988 KB Output is correct
9 Correct 627 ms 23500 KB Output is correct
10 Correct 500 ms 21612 KB Output is correct
11 Correct 441 ms 23448 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 5 ms 596 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 6 ms 576 KB Output is correct
20 Correct 6 ms 540 KB Output is correct
21 Correct 6 ms 568 KB Output is correct
22 Correct 5 ms 556 KB Output is correct
23 Correct 5 ms 596 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 5 ms 596 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 6 ms 576 KB Output is correct
20 Correct 6 ms 540 KB Output is correct
21 Correct 6 ms 568 KB Output is correct
22 Correct 5 ms 556 KB Output is correct
23 Correct 5 ms 596 KB Output is correct
24 Correct 567 ms 23380 KB Output is correct
25 Correct 479 ms 21564 KB Output is correct
26 Correct 551 ms 21616 KB Output is correct
27 Correct 509 ms 21724 KB Output is correct
28 Correct 591 ms 22404 KB Output is correct
29 Correct 549 ms 23300 KB Output is correct
30 Correct 732 ms 21560 KB Output is correct
31 Correct 210 ms 6092 KB Output is correct
32 Correct 307 ms 16988 KB Output is correct
33 Correct 594 ms 20708 KB Output is correct
34 Correct 690 ms 21652 KB Output is correct
35 Correct 593 ms 21668 KB Output is correct
36 Correct 569 ms 21568 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 5 ms 596 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 6 ms 576 KB Output is correct
20 Correct 6 ms 540 KB Output is correct
21 Correct 6 ms 568 KB Output is correct
22 Correct 5 ms 556 KB Output is correct
23 Correct 5 ms 596 KB Output is correct
24 Correct 567 ms 23380 KB Output is correct
25 Correct 479 ms 21564 KB Output is correct
26 Correct 551 ms 21616 KB Output is correct
27 Correct 509 ms 21724 KB Output is correct
28 Correct 591 ms 22404 KB Output is correct
29 Correct 549 ms 23300 KB Output is correct
30 Correct 732 ms 21560 KB Output is correct
31 Correct 210 ms 6092 KB Output is correct
32 Correct 307 ms 16988 KB Output is correct
33 Correct 594 ms 20708 KB Output is correct
34 Correct 690 ms 21652 KB Output is correct
35 Correct 593 ms 21668 KB Output is correct
36 Correct 569 ms 21568 KB Output is correct
37 Correct 684 ms 21916 KB Output is correct
38 Correct 586 ms 21848 KB Output is correct
39 Correct 603 ms 21612 KB Output is correct
40 Correct 606 ms 21608 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 821 ms 21968 KB Output is correct
43 Correct 654 ms 21028 KB Output is correct
44 Correct 777 ms 21944 KB Output is correct
45 Correct 649 ms 21600 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 5 ms 596 KB Output is correct
18 Correct 5 ms 596 KB Output is correct
19 Correct 6 ms 576 KB Output is correct
20 Correct 6 ms 540 KB Output is correct
21 Correct 6 ms 568 KB Output is correct
22 Correct 5 ms 556 KB Output is correct
23 Correct 5 ms 596 KB Output is correct
24 Correct 567 ms 23380 KB Output is correct
25 Correct 479 ms 21564 KB Output is correct
26 Correct 551 ms 21616 KB Output is correct
27 Correct 509 ms 21724 KB Output is correct
28 Correct 591 ms 22404 KB Output is correct
29 Correct 549 ms 23300 KB Output is correct
30 Correct 732 ms 21560 KB Output is correct
31 Correct 210 ms 6092 KB Output is correct
32 Correct 307 ms 16988 KB Output is correct
33 Correct 594 ms 20708 KB Output is correct
34 Correct 690 ms 21652 KB Output is correct
35 Correct 593 ms 21668 KB Output is correct
36 Correct 569 ms 21568 KB Output is correct
37 Correct 684 ms 21916 KB Output is correct
38 Correct 586 ms 21848 KB Output is correct
39 Correct 603 ms 21612 KB Output is correct
40 Correct 606 ms 21608 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 821 ms 21968 KB Output is correct
43 Correct 654 ms 21028 KB Output is correct
44 Correct 777 ms 21944 KB Output is correct
45 Correct 649 ms 21600 KB Output is correct
46 Correct 3550 ms 96316 KB Output is correct
47 Correct 3358 ms 100104 KB Output is correct
48 Correct 3192 ms 99152 KB Output is correct
49 Correct 3290 ms 99172 KB Output is correct
50 Correct 4962 ms 99728 KB Output is correct
51 Correct 3602 ms 92988 KB Output is correct
52 Correct 4069 ms 98472 KB Output is correct
53 Correct 3844 ms 97148 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 21844 KB Output is correct
2 Correct 677 ms 21840 KB Output is correct
3 Correct 612 ms 23332 KB Output is correct
4 Correct 603 ms 20800 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 641 ms 21480 KB Output is correct
7 Correct 244 ms 6296 KB Output is correct
8 Correct 329 ms 17988 KB Output is correct
9 Correct 627 ms 23500 KB Output is correct
10 Correct 500 ms 21612 KB Output is correct
11 Correct 441 ms 23448 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 312 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 304 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 304 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 5 ms 596 KB Output is correct
29 Correct 5 ms 596 KB Output is correct
30 Correct 6 ms 576 KB Output is correct
31 Correct 6 ms 540 KB Output is correct
32 Correct 6 ms 568 KB Output is correct
33 Correct 5 ms 556 KB Output is correct
34 Correct 5 ms 596 KB Output is correct
35 Correct 567 ms 23380 KB Output is correct
36 Correct 479 ms 21564 KB Output is correct
37 Correct 551 ms 21616 KB Output is correct
38 Correct 509 ms 21724 KB Output is correct
39 Correct 591 ms 22404 KB Output is correct
40 Correct 549 ms 23300 KB Output is correct
41 Correct 732 ms 21560 KB Output is correct
42 Correct 210 ms 6092 KB Output is correct
43 Correct 307 ms 16988 KB Output is correct
44 Correct 594 ms 20708 KB Output is correct
45 Correct 690 ms 21652 KB Output is correct
46 Correct 593 ms 21668 KB Output is correct
47 Correct 569 ms 21568 KB Output is correct
48 Correct 684 ms 21916 KB Output is correct
49 Correct 586 ms 21848 KB Output is correct
50 Correct 603 ms 21612 KB Output is correct
51 Correct 606 ms 21608 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 821 ms 21968 KB Output is correct
54 Correct 654 ms 21028 KB Output is correct
55 Correct 777 ms 21944 KB Output is correct
56 Correct 649 ms 21600 KB Output is correct
57 Correct 679 ms 21764 KB Output is correct
58 Incorrect 621 ms 21404 KB Output isn't correct
59 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 21844 KB Output is correct
2 Correct 677 ms 21840 KB Output is correct
3 Correct 612 ms 23332 KB Output is correct
4 Correct 603 ms 20800 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 641 ms 21480 KB Output is correct
7 Correct 244 ms 6296 KB Output is correct
8 Correct 329 ms 17988 KB Output is correct
9 Correct 627 ms 23500 KB Output is correct
10 Correct 500 ms 21612 KB Output is correct
11 Correct 441 ms 23448 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 1 ms 312 KB Output is correct
15 Correct 1 ms 304 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 312 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 312 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 304 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 304 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 5 ms 596 KB Output is correct
29 Correct 5 ms 596 KB Output is correct
30 Correct 6 ms 576 KB Output is correct
31 Correct 6 ms 540 KB Output is correct
32 Correct 6 ms 568 KB Output is correct
33 Correct 5 ms 556 KB Output is correct
34 Correct 5 ms 596 KB Output is correct
35 Correct 567 ms 23380 KB Output is correct
36 Correct 479 ms 21564 KB Output is correct
37 Correct 551 ms 21616 KB Output is correct
38 Correct 509 ms 21724 KB Output is correct
39 Correct 591 ms 22404 KB Output is correct
40 Correct 549 ms 23300 KB Output is correct
41 Correct 732 ms 21560 KB Output is correct
42 Correct 210 ms 6092 KB Output is correct
43 Correct 307 ms 16988 KB Output is correct
44 Correct 594 ms 20708 KB Output is correct
45 Correct 690 ms 21652 KB Output is correct
46 Correct 593 ms 21668 KB Output is correct
47 Correct 569 ms 21568 KB Output is correct
48 Correct 684 ms 21916 KB Output is correct
49 Correct 586 ms 21848 KB Output is correct
50 Correct 603 ms 21612 KB Output is correct
51 Correct 606 ms 21608 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 821 ms 21968 KB Output is correct
54 Correct 654 ms 21028 KB Output is correct
55 Correct 777 ms 21944 KB Output is correct
56 Correct 649 ms 21600 KB Output is correct
57 Correct 3550 ms 96316 KB Output is correct
58 Correct 3358 ms 100104 KB Output is correct
59 Correct 3192 ms 99152 KB Output is correct
60 Correct 3290 ms 99172 KB Output is correct
61 Correct 4962 ms 99728 KB Output is correct
62 Correct 3602 ms 92988 KB Output is correct
63 Correct 4069 ms 98472 KB Output is correct
64 Correct 3844 ms 97148 KB Output is correct
65 Correct 679 ms 21764 KB Output is correct
66 Incorrect 621 ms 21404 KB Output isn't correct
67 Halted 0 ms 0 KB -