oj.uz

Submission #348885

# Submission time Handle Problem Language Result Execution time Memory
348885 2021-01-16T04:00:14 Z ijxjdjd Two Dishes (JOI19_dishes) C++14
74 / 100
 5247 ms 193088 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;
const int MAXN = (int)(1e6)+5;
ll A[MAXN];
ll S[MAXN];
ll B[MAXN];
ll T[MAXN];
ll P[MAXN];
ll Q[MAXN];
ll prefA[MAXN];
ll prefB[MAXN];
ll lzy[4*MAXN];
ll mx[4*MAXN];
void push(int n) {
    lzy[2*n] += lzy[n];
    lzy[2*n+1] += lzy[n];
    mx[2*n] += lzy[n];
    mx[2*n+1] += lzy[n];
    lzy[n] = 0;
}
void add(int n, int tl, int tr, int l, int r, ll ad) {
    if (tr < l || r < tl) {
        return;
    }
    if (l <= tl && tr <= r) {
        lzy[n] += ad;
        mx[n] += ad;
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        add(2*n, tl, tm, l, r, ad);
        add(2*n+1, tm+1, tr, l, r, ad);
        mx[n] = max(mx[2*n], mx[2*n+1]);
    }
}
ll query(int n, int tl, int tr, int l, int r) {
   if (tr < l || r < tl) {
        return ll(-1e18);
    }
    if (l <= tl && tr <= r) {
        return mx[n];
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        return max(query(2*n, tl, tm, l, r), query(2*n+1, tm+1, tr, l, r));
    }
}
void upd(int n, int tl, int tr, int i, ll val) {
    if (tl == tr) {
        mx[n] = max(mx[n], val);
        lzy[n] = 0;
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        if (i <= tm) {
            upd(2*n, tl, tm, i, val);
        }
        else {
            upd(2*n+1, tm+1, tr, i, val);
        }
        mx[n] = max(mx[2*n], mx[2*n+1]);
    }
}
vector<pair<int, ll>> row[MAXN];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, M;
	cin >> N >> M;
	FR(i, 4*MAXN) {
        mx[i] = (ll)(-1e18);
	}
	for (int i = 1; i <= N; i++) {
        cin >> A[i] >> S[i] >> P[i];
        prefA[i] = A[i] + prefA[i-1];
	}
	for (int i = 1; i <= M; i++) {
        cin >> B[i] >> T[i] >> Q[i];
        prefB[i] = B[i] + prefB[i-1];
	}
	ll offset = 0;
	for (int i = 1; i <= N; i++) {
        if (prefA[i] <= S[i]) {
            int low = 0;
            int high = M;
            ll g = S[i] - prefA[i];
            while (low < high) {
                int mid = (low + high+1)/2;
                if (prefB[mid] <= g) {
                    low = mid;
                }
                else {
                    high = mid-1;
                }
            }
            row[i].push_back({low, P[i]});
        }
	}
	for (int i = 1; i <= M; i++) {
        if (prefB[i] <= T[i]) {
            int low = 0;
            int high = N;
            ll g = T[i] - prefB[i];
            while (low < high) {
                int mid = (low + high+1)/2;
                if (prefA[mid] <= g) {
                    low = mid;
                }
                else {
                    high = mid-1;
                }
            }
            offset += Q[i];
            if (low != N+1) {
                row[low+1].push_back({i-1, -Q[i]});
            }
        }
	}
	upd(1, 0, MAXN, 0, 0);
	FR(i, N+2) {
        sort(row[i].begin(), row[i].end());
        while (row[i].size()) {
            while (row[i].size() != 1) {
                if (row[i][row[i].size()-1].first == row[i][row[i].size()-2].first) {
                    row[i][row[i].size()-2].second += row[i][row[i].size()-1].second;
                    row[i].pop_back();
                }
                else {
                    break;
                }
            }
            upd(1, 0, MAXN, row[i].back().first+1, query(1, 0, MAXN, 0, row[i].back().first));
            add(1, 0, MAXN, 0, row[i].back().first, row[i].back().second);
            row[i].pop_back();
        }
	}
	cout << mx[1] + offset;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 81388 KB Output is correct
2 Correct 507 ms 82280 KB Output is correct
3 Correct 592 ms 81236 KB Output is correct
4 Correct 349 ms 76140 KB Output is correct
5 Correct 33 ms 55276 KB Output is correct
6 Correct 513 ms 81252 KB Output is correct
7 Correct 296 ms 68188 KB Output is correct
8 Correct 298 ms 68588 KB Output is correct
9 Correct 602 ms 81316 KB Output is correct
10 Correct 400 ms 81260 KB Output is correct
11 Correct 551 ms 81492 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55276 KB Output is correct
2 Correct 32 ms 55276 KB Output is correct
3 Correct 33 ms 55276 KB Output is correct
4 Correct 35 ms 55276 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 33 ms 55276 KB Output is correct
7 Correct 33 ms 55276 KB Output is correct
8 Correct 33 ms 55276 KB Output is correct
9 Correct 33 ms 55276 KB Output is correct
10 Correct 34 ms 55276 KB Output is correct
11 Correct 33 ms 55276 KB Output is correct
12 Correct 33 ms 55276 KB Output is correct
13 Correct 33 ms 55296 KB Output is correct
14 Correct 33 ms 55276 KB Output is correct
15 Correct 33 ms 55276 KB Output is correct
16 Correct 33 ms 55276 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55276 KB Output is correct
2 Correct 32 ms 55276 KB Output is correct
3 Correct 33 ms 55276 KB Output is correct
4 Correct 35 ms 55276 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 33 ms 55276 KB Output is correct
7 Correct 33 ms 55276 KB Output is correct
8 Correct 33 ms 55276 KB Output is correct
9 Correct 33 ms 55276 KB Output is correct
10 Correct 34 ms 55276 KB Output is correct
11 Correct 33 ms 55276 KB Output is correct
12 Correct 33 ms 55276 KB Output is correct
13 Correct 33 ms 55296 KB Output is correct
14 Correct 33 ms 55276 KB Output is correct
15 Correct 33 ms 55276 KB Output is correct
16 Correct 33 ms 55276 KB Output is correct
17 Correct 36 ms 55660 KB Output is correct
18 Correct 40 ms 55660 KB Output is correct
19 Correct 39 ms 55660 KB Output is correct
20 Correct 38 ms 55660 KB Output is correct
21 Correct 39 ms 55660 KB Output is correct
22 Correct 39 ms 55660 KB Output is correct
23 Correct 39 ms 55532 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55276 KB Output is correct
2 Correct 32 ms 55276 KB Output is correct
3 Correct 33 ms 55276 KB Output is correct
4 Correct 35 ms 55276 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 33 ms 55276 KB Output is correct
7 Correct 33 ms 55276 KB Output is correct
8 Correct 33 ms 55276 KB Output is correct
9 Correct 33 ms 55276 KB Output is correct
10 Correct 34 ms 55276 KB Output is correct
11 Correct 33 ms 55276 KB Output is correct
12 Correct 33 ms 55276 KB Output is correct
13 Correct 33 ms 55296 KB Output is correct
14 Correct 33 ms 55276 KB Output is correct
15 Correct 33 ms 55276 KB Output is correct
16 Correct 33 ms 55276 KB Output is correct
17 Correct 36 ms 55660 KB Output is correct
18 Correct 40 ms 55660 KB Output is correct
19 Correct 39 ms 55660 KB Output is correct
20 Correct 38 ms 55660 KB Output is correct
21 Correct 39 ms 55660 KB Output is correct
22 Correct 39 ms 55660 KB Output is correct
23 Correct 39 ms 55532 KB Output is correct
24 Correct 464 ms 79836 KB Output is correct
25 Correct 465 ms 78292 KB Output is correct
26 Correct 487 ms 79836 KB Output is correct
27 Correct 490 ms 79636 KB Output is correct
28 Correct 615 ms 80988 KB Output is correct
29 Correct 573 ms 81364 KB Output is correct
30 Correct 866 ms 83564 KB Output is correct
31 Correct 298 ms 68688 KB Output is correct
32 Correct 286 ms 68460 KB Output is correct
33 Correct 505 ms 77292 KB Output is correct
34 Correct 771 ms 82384 KB Output is correct
35 Correct 821 ms 83168 KB Output is correct
36 Correct 804 ms 83032 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55276 KB Output is correct
2 Correct 32 ms 55276 KB Output is correct
3 Correct 33 ms 55276 KB Output is correct
4 Correct 35 ms 55276 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 33 ms 55276 KB Output is correct
7 Correct 33 ms 55276 KB Output is correct
8 Correct 33 ms 55276 KB Output is correct
9 Correct 33 ms 55276 KB Output is correct
10 Correct 34 ms 55276 KB Output is correct
11 Correct 33 ms 55276 KB Output is correct
12 Correct 33 ms 55276 KB Output is correct
13 Correct 33 ms 55296 KB Output is correct
14 Correct 33 ms 55276 KB Output is correct
15 Correct 33 ms 55276 KB Output is correct
16 Correct 33 ms 55276 KB Output is correct
17 Correct 36 ms 55660 KB Output is correct
18 Correct 40 ms 55660 KB Output is correct
19 Correct 39 ms 55660 KB Output is correct
20 Correct 38 ms 55660 KB Output is correct
21 Correct 39 ms 55660 KB Output is correct
22 Correct 39 ms 55660 KB Output is correct
23 Correct 39 ms 55532 KB Output is correct
24 Correct 464 ms 79836 KB Output is correct
25 Correct 465 ms 78292 KB Output is correct
26 Correct 487 ms 79836 KB Output is correct
27 Correct 490 ms 79636 KB Output is correct
28 Correct 615 ms 80988 KB Output is correct
29 Correct 573 ms 81364 KB Output is correct
30 Correct 866 ms 83564 KB Output is correct
31 Correct 298 ms 68688 KB Output is correct
32 Correct 286 ms 68460 KB Output is correct
33 Correct 505 ms 77292 KB Output is correct
34 Correct 771 ms 82384 KB Output is correct
35 Correct 821 ms 83168 KB Output is correct
36 Correct 804 ms 83032 KB Output is correct
37 Correct 517 ms 79808 KB Output is correct
38 Correct 520 ms 79724 KB Output is correct
39 Correct 430 ms 81260 KB Output is correct
40 Correct 420 ms 81260 KB Output is correct
41 Correct 33 ms 55276 KB Output is correct
42 Correct 887 ms 83436 KB Output is correct
43 Correct 536 ms 77224 KB Output is correct
44 Correct 786 ms 82108 KB Output is correct
45 Correct 843 ms 83352 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 55276 KB Output is correct
2 Correct 32 ms 55276 KB Output is correct
3 Correct 33 ms 55276 KB Output is correct
4 Correct 35 ms 55276 KB Output is correct
5 Correct 34 ms 55276 KB Output is correct
6 Correct 33 ms 55276 KB Output is correct
7 Correct 33 ms 55276 KB Output is correct
8 Correct 33 ms 55276 KB Output is correct
9 Correct 33 ms 55276 KB Output is correct
10 Correct 34 ms 55276 KB Output is correct
11 Correct 33 ms 55276 KB Output is correct
12 Correct 33 ms 55276 KB Output is correct
13 Correct 33 ms 55296 KB Output is correct
14 Correct 33 ms 55276 KB Output is correct
15 Correct 33 ms 55276 KB Output is correct
16 Correct 33 ms 55276 KB Output is correct
17 Correct 36 ms 55660 KB Output is correct
18 Correct 40 ms 55660 KB Output is correct
19 Correct 39 ms 55660 KB Output is correct
20 Correct 38 ms 55660 KB Output is correct
21 Correct 39 ms 55660 KB Output is correct
22 Correct 39 ms 55660 KB Output is correct
23 Correct 39 ms 55532 KB Output is correct
24 Correct 464 ms 79836 KB Output is correct
25 Correct 465 ms 78292 KB Output is correct
26 Correct 487 ms 79836 KB Output is correct
27 Correct 490 ms 79636 KB Output is correct
28 Correct 615 ms 80988 KB Output is correct
29 Correct 573 ms 81364 KB Output is correct
30 Correct 866 ms 83564 KB Output is correct
31 Correct 298 ms 68688 KB Output is correct
32 Correct 286 ms 68460 KB Output is correct
33 Correct 505 ms 77292 KB Output is correct
34 Correct 771 ms 82384 KB Output is correct
35 Correct 821 ms 83168 KB Output is correct
36 Correct 804 ms 83032 KB Output is correct
37 Correct 517 ms 79808 KB Output is correct
38 Correct 520 ms 79724 KB Output is correct
39 Correct 430 ms 81260 KB Output is correct
40 Correct 420 ms 81260 KB Output is correct
41 Correct 33 ms 55276 KB Output is correct
42 Correct 887 ms 83436 KB Output is correct
43 Correct 536 ms 77224 KB Output is correct
44 Correct 786 ms 82108 KB Output is correct
45 Correct 843 ms 83352 KB Output is correct
46 Correct 2461 ms 173588 KB Output is correct
47 Correct 2453 ms 173720 KB Output is correct
48 Correct 1931 ms 181740 KB Output is correct
49 Correct 1939 ms 181656 KB Output is correct
50 Correct 5247 ms 193088 KB Output is correct
51 Correct 2983 ms 159712 KB Output is correct
52 Correct 4168 ms 181908 KB Output is correct
53 Correct 4869 ms 191776 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 81388 KB Output is correct
2 Correct 507 ms 82280 KB Output is correct
3 Correct 592 ms 81236 KB Output is correct
4 Correct 349 ms 76140 KB Output is correct
5 Correct 33 ms 55276 KB Output is correct
6 Correct 513 ms 81252 KB Output is correct
7 Correct 296 ms 68188 KB Output is correct
8 Correct 298 ms 68588 KB Output is correct
9 Correct 602 ms 81316 KB Output is correct
10 Correct 400 ms 81260 KB Output is correct
11 Correct 551 ms 81492 KB Output is correct
12 Correct 32 ms 55276 KB Output is correct
13 Correct 32 ms 55276 KB Output is correct
14 Correct 33 ms 55276 KB Output is correct
15 Correct 35 ms 55276 KB Output is correct
16 Correct 34 ms 55276 KB Output is correct
17 Correct 33 ms 55276 KB Output is correct
18 Correct 33 ms 55276 KB Output is correct
19 Correct 33 ms 55276 KB Output is correct
20 Correct 33 ms 55276 KB Output is correct
21 Correct 34 ms 55276 KB Output is correct
22 Correct 33 ms 55276 KB Output is correct
23 Correct 33 ms 55276 KB Output is correct
24 Correct 33 ms 55296 KB Output is correct
25 Correct 33 ms 55276 KB Output is correct
26 Correct 33 ms 55276 KB Output is correct
27 Correct 33 ms 55276 KB Output is correct
28 Correct 36 ms 55660 KB Output is correct
29 Correct 40 ms 55660 KB Output is correct
30 Correct 39 ms 55660 KB Output is correct
31 Correct 38 ms 55660 KB Output is correct
32 Correct 39 ms 55660 KB Output is correct
33 Correct 39 ms 55660 KB Output is correct
34 Correct 39 ms 55532 KB Output is correct
35 Correct 464 ms 79836 KB Output is correct
36 Correct 465 ms 78292 KB Output is correct
37 Correct 487 ms 79836 KB Output is correct
38 Correct 490 ms 79636 KB Output is correct
39 Correct 615 ms 80988 KB Output is correct
40 Correct 573 ms 81364 KB Output is correct
41 Correct 866 ms 83564 KB Output is correct
42 Correct 298 ms 68688 KB Output is correct
43 Correct 286 ms 68460 KB Output is correct
44 Correct 505 ms 77292 KB Output is correct
45 Correct 771 ms 82384 KB Output is correct
46 Correct 821 ms 83168 KB Output is correct
47 Correct 804 ms 83032 KB Output is correct
48 Correct 517 ms 79808 KB Output is correct
49 Correct 520 ms 79724 KB Output is correct
50 Correct 430 ms 81260 KB Output is correct
51 Correct 420 ms 81260 KB Output is correct
52 Correct 33 ms 55276 KB Output is correct
53 Correct 887 ms 83436 KB Output is correct
54 Correct 536 ms 77224 KB Output is correct
55 Correct 786 ms 82108 KB Output is correct
56 Correct 843 ms 83352 KB Output is correct
57 Incorrect 523 ms 79324 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 81388 KB Output is correct
2 Correct 507 ms 82280 KB Output is correct
3 Correct 592 ms 81236 KB Output is correct
4 Correct 349 ms 76140 KB Output is correct
5 Correct 33 ms 55276 KB Output is correct
6 Correct 513 ms 81252 KB Output is correct
7 Correct 296 ms 68188 KB Output is correct
8 Correct 298 ms 68588 KB Output is correct
9 Correct 602 ms 81316 KB Output is correct
10 Correct 400 ms 81260 KB Output is correct
11 Correct 551 ms 81492 KB Output is correct
12 Correct 32 ms 55276 KB Output is correct
13 Correct 32 ms 55276 KB Output is correct
14 Correct 33 ms 55276 KB Output is correct
15 Correct 35 ms 55276 KB Output is correct
16 Correct 34 ms 55276 KB Output is correct
17 Correct 33 ms 55276 KB Output is correct
18 Correct 33 ms 55276 KB Output is correct
19 Correct 33 ms 55276 KB Output is correct
20 Correct 33 ms 55276 KB Output is correct
21 Correct 34 ms 55276 KB Output is correct
22 Correct 33 ms 55276 KB Output is correct
23 Correct 33 ms 55276 KB Output is correct
24 Correct 33 ms 55296 KB Output is correct
25 Correct 33 ms 55276 KB Output is correct
26 Correct 33 ms 55276 KB Output is correct
27 Correct 33 ms 55276 KB Output is correct
28 Correct 36 ms 55660 KB Output is correct
29 Correct 40 ms 55660 KB Output is correct
30 Correct 39 ms 55660 KB Output is correct
31 Correct 38 ms 55660 KB Output is correct
32 Correct 39 ms 55660 KB Output is correct
33 Correct 39 ms 55660 KB Output is correct
34 Correct 39 ms 55532 KB Output is correct
35 Correct 464 ms 79836 KB Output is correct
36 Correct 465 ms 78292 KB Output is correct
37 Correct 487 ms 79836 KB Output is correct
38 Correct 490 ms 79636 KB Output is correct
39 Correct 615 ms 80988 KB Output is correct
40 Correct 573 ms 81364 KB Output is correct
41 Correct 866 ms 83564 KB Output is correct
42 Correct 298 ms 68688 KB Output is correct
43 Correct 286 ms 68460 KB Output is correct
44 Correct 505 ms 77292 KB Output is correct
45 Correct 771 ms 82384 KB Output is correct
46 Correct 821 ms 83168 KB Output is correct
47 Correct 804 ms 83032 KB Output is correct
48 Correct 517 ms 79808 KB Output is correct
49 Correct 520 ms 79724 KB Output is correct
50 Correct 430 ms 81260 KB Output is correct
51 Correct 420 ms 81260 KB Output is correct
52 Correct 33 ms 55276 KB Output is correct
53 Correct 887 ms 83436 KB Output is correct
54 Correct 536 ms 77224 KB Output is correct
55 Correct 786 ms 82108 KB Output is correct
56 Correct 843 ms 83352 KB Output is correct
57 Correct 2461 ms 173588 KB Output is correct
58 Correct 2453 ms 173720 KB Output is correct
59 Correct 1931 ms 181740 KB Output is correct
60 Correct 1939 ms 181656 KB Output is correct
61 Correct 5247 ms 193088 KB Output is correct
62 Correct 2983 ms 159712 KB Output is correct
63 Correct 4168 ms 181908 KB Output is correct
64 Correct 4869 ms 191776 KB Output is correct
65 Incorrect 523 ms 79324 KB Output isn't correct
66 Halted 0 ms 0 KB -