oj.uz

Submission #579484

# Submission time Handle Problem Language Result Execution time Memory
579484 2022-06-19T08:50:49 Z Lucpp Two Dishes (JOI19_dishes) C++17
65 / 100
 972 ms 40536 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAX = 2e5+2;

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

struct SumSeg{
    vector<ll> S;
    int cap;
    void init(int n){
        for(cap = 1; cap < n; cap*=2);
        S.resize(2*cap);
    }
    void upd(int i, ll v){
        i += cap;
        S[i] = v;
        while(i > 1){
            i /= 2;
            S[i] = S[2*i]+S[2*i+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 0;
        int m = (a+b)/2;
        return 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);}
};
struct MaxSeg{
    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);
            // cerr << j << " " << B[i][j] << " " << P[i][j] << "\n";
        }
        // cerr << "\n";
    }
    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());

    SumSeg sumSeg; sumSeg.init(n);
    for(int i = 0; i < n; ++i){
        if(B[0][i] >= 0) sumSeg.upd(i, P[0][i]);
    }
    MaxSeg maxSeg; maxSeg.init(n);
    maxSeg.upd(1, sumSeg.qry(1, n));

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 25824 KB Output is correct
2 Correct 730 ms 38608 KB Output is correct
3 Correct 654 ms 40324 KB Output is correct
4 Correct 676 ms 38400 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 744 ms 38624 KB Output is correct
7 Correct 257 ms 12544 KB Output is correct
8 Correct 328 ms 28492 KB Output is correct
9 Correct 694 ms 40536 KB Output is correct
10 Correct 578 ms 32584 KB Output is correct
11 Correct 466 ms 34760 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 312 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 312 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 312 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 6 ms 596 KB Output is correct
18 Correct 6 ms 576 KB Output is correct
19 Correct 7 ms 596 KB Output is correct
20 Correct 6 ms 596 KB Output is correct
21 Correct 6 ms 596 KB Output is correct
22 Correct 5 ms 596 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 316 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 312 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 6 ms 596 KB Output is correct
18 Correct 6 ms 576 KB Output is correct
19 Correct 7 ms 596 KB Output is correct
20 Correct 6 ms 596 KB Output is correct
21 Correct 6 ms 596 KB Output is correct
22 Correct 5 ms 596 KB Output is correct
23 Correct 5 ms 596 KB Output is correct
24 Correct 607 ms 27408 KB Output is correct
25 Correct 578 ms 35920 KB Output is correct
26 Correct 638 ms 35856 KB Output is correct
27 Correct 532 ms 35908 KB Output is correct
28 Correct 668 ms 36820 KB Output is correct
29 Correct 616 ms 38436 KB Output is correct
30 Correct 878 ms 35932 KB Output is correct
31 Correct 225 ms 10964 KB Output is correct
32 Correct 345 ms 25772 KB Output is correct
33 Correct 642 ms 34752 KB Output is correct
34 Correct 801 ms 36132 KB Output is correct
35 Correct 637 ms 29504 KB Output is correct
36 Correct 644 ms 29540 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 312 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 6 ms 596 KB Output is correct
18 Correct 6 ms 576 KB Output is correct
19 Correct 7 ms 596 KB Output is correct
20 Correct 6 ms 596 KB Output is correct
21 Correct 6 ms 596 KB Output is correct
22 Correct 5 ms 596 KB Output is correct
23 Correct 5 ms 596 KB Output is correct
24 Correct 607 ms 27408 KB Output is correct
25 Correct 578 ms 35920 KB Output is correct
26 Correct 638 ms 35856 KB Output is correct
27 Correct 532 ms 35908 KB Output is correct
28 Correct 668 ms 36820 KB Output is correct
29 Correct 616 ms 38436 KB Output is correct
30 Correct 878 ms 35932 KB Output is correct
31 Correct 225 ms 10964 KB Output is correct
32 Correct 345 ms 25772 KB Output is correct
33 Correct 642 ms 34752 KB Output is correct
34 Correct 801 ms 36132 KB Output is correct
35 Correct 637 ms 29504 KB Output is correct
36 Correct 644 ms 29540 KB Output is correct
37 Correct 746 ms 35880 KB Output is correct
38 Correct 650 ms 35732 KB Output is correct
39 Correct 648 ms 36468 KB Output is correct
40 Correct 660 ms 36252 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 968 ms 35752 KB Output is correct
43 Correct 756 ms 35024 KB Output is correct
44 Correct 972 ms 35960 KB Output is correct
45 Correct 818 ms 32684 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 312 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 6 ms 596 KB Output is correct
18 Correct 6 ms 576 KB Output is correct
19 Correct 7 ms 596 KB Output is correct
20 Correct 6 ms 596 KB Output is correct
21 Correct 6 ms 596 KB Output is correct
22 Correct 5 ms 596 KB Output is correct
23 Correct 5 ms 596 KB Output is correct
24 Correct 607 ms 27408 KB Output is correct
25 Correct 578 ms 35920 KB Output is correct
26 Correct 638 ms 35856 KB Output is correct
27 Correct 532 ms 35908 KB Output is correct
28 Correct 668 ms 36820 KB Output is correct
29 Correct 616 ms 38436 KB Output is correct
30 Correct 878 ms 35932 KB Output is correct
31 Correct 225 ms 10964 KB Output is correct
32 Correct 345 ms 25772 KB Output is correct
33 Correct 642 ms 34752 KB Output is correct
34 Correct 801 ms 36132 KB Output is correct
35 Correct 637 ms 29504 KB Output is correct
36 Correct 644 ms 29540 KB Output is correct
37 Correct 746 ms 35880 KB Output is correct
38 Correct 650 ms 35732 KB Output is correct
39 Correct 648 ms 36468 KB Output is correct
40 Correct 660 ms 36252 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 968 ms 35752 KB Output is correct
43 Correct 756 ms 35024 KB Output is correct
44 Correct 972 ms 35960 KB Output is correct
45 Correct 818 ms 32684 KB Output is correct
46 Runtime error 611 ms 23444 KB Execution killed with signal 11
47 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 25824 KB Output is correct
2 Correct 730 ms 38608 KB Output is correct
3 Correct 654 ms 40324 KB Output is correct
4 Correct 676 ms 38400 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 744 ms 38624 KB Output is correct
7 Correct 257 ms 12544 KB Output is correct
8 Correct 328 ms 28492 KB Output is correct
9 Correct 694 ms 40536 KB Output is correct
10 Correct 578 ms 32584 KB Output is correct
11 Correct 466 ms 34760 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 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 312 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 312 KB Output is correct
28 Correct 6 ms 596 KB Output is correct
29 Correct 6 ms 576 KB Output is correct
30 Correct 7 ms 596 KB Output is correct
31 Correct 6 ms 596 KB Output is correct
32 Correct 6 ms 596 KB Output is correct
33 Correct 5 ms 596 KB Output is correct
34 Correct 5 ms 596 KB Output is correct
35 Correct 607 ms 27408 KB Output is correct
36 Correct 578 ms 35920 KB Output is correct
37 Correct 638 ms 35856 KB Output is correct
38 Correct 532 ms 35908 KB Output is correct
39 Correct 668 ms 36820 KB Output is correct
40 Correct 616 ms 38436 KB Output is correct
41 Correct 878 ms 35932 KB Output is correct
42 Correct 225 ms 10964 KB Output is correct
43 Correct 345 ms 25772 KB Output is correct
44 Correct 642 ms 34752 KB Output is correct
45 Correct 801 ms 36132 KB Output is correct
46 Correct 637 ms 29504 KB Output is correct
47 Correct 644 ms 29540 KB Output is correct
48 Correct 746 ms 35880 KB Output is correct
49 Correct 650 ms 35732 KB Output is correct
50 Correct 648 ms 36468 KB Output is correct
51 Correct 660 ms 36252 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 968 ms 35752 KB Output is correct
54 Correct 756 ms 35024 KB Output is correct
55 Correct 972 ms 35960 KB Output is correct
56 Correct 818 ms 32684 KB Output is correct
57 Correct 853 ms 31460 KB Output is correct
58 Incorrect 696 ms 39448 KB Output isn't correct
59 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 25824 KB Output is correct
2 Correct 730 ms 38608 KB Output is correct
3 Correct 654 ms 40324 KB Output is correct
4 Correct 676 ms 38400 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 744 ms 38624 KB Output is correct
7 Correct 257 ms 12544 KB Output is correct
8 Correct 328 ms 28492 KB Output is correct
9 Correct 694 ms 40536 KB Output is correct
10 Correct 578 ms 32584 KB Output is correct
11 Correct 466 ms 34760 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 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 312 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 312 KB Output is correct
28 Correct 6 ms 596 KB Output is correct
29 Correct 6 ms 576 KB Output is correct
30 Correct 7 ms 596 KB Output is correct
31 Correct 6 ms 596 KB Output is correct
32 Correct 6 ms 596 KB Output is correct
33 Correct 5 ms 596 KB Output is correct
34 Correct 5 ms 596 KB Output is correct
35 Correct 607 ms 27408 KB Output is correct
36 Correct 578 ms 35920 KB Output is correct
37 Correct 638 ms 35856 KB Output is correct
38 Correct 532 ms 35908 KB Output is correct
39 Correct 668 ms 36820 KB Output is correct
40 Correct 616 ms 38436 KB Output is correct
41 Correct 878 ms 35932 KB Output is correct
42 Correct 225 ms 10964 KB Output is correct
43 Correct 345 ms 25772 KB Output is correct
44 Correct 642 ms 34752 KB Output is correct
45 Correct 801 ms 36132 KB Output is correct
46 Correct 637 ms 29504 KB Output is correct
47 Correct 644 ms 29540 KB Output is correct
48 Correct 746 ms 35880 KB Output is correct
49 Correct 650 ms 35732 KB Output is correct
50 Correct 648 ms 36468 KB Output is correct
51 Correct 660 ms 36252 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 968 ms 35752 KB Output is correct
54 Correct 756 ms 35024 KB Output is correct
55 Correct 972 ms 35960 KB Output is correct
56 Correct 818 ms 32684 KB Output is correct
57 Runtime error 611 ms 23444 KB Execution killed with signal 11
58 Halted 0 ms 0 KB -