oj.uz

Submission #348881

# Submission time Handle Problem Language Result Execution time Memory
348881 2021-01-16T03:48:27 Z ijxjdjd Two Dishes (JOI19_dishes) C++14
74 / 100
 5281 ms 194152 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];
            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 81644 KB Output is correct
2 Correct 509 ms 82408 KB Output is correct
3 Correct 599 ms 81620 KB Output is correct
4 Correct 349 ms 76396 KB Output is correct
5 Correct 35 ms 55276 KB Output is correct
6 Correct 510 ms 81636 KB Output is correct
7 Correct 298 ms 68316 KB Output is correct
8 Correct 298 ms 71020 KB Output is correct
9 Correct 600 ms 83796 KB Output is correct
10 Correct 382 ms 83784 KB Output is correct
11 Correct 549 ms 83944 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 55276 KB Output is correct
2 Correct 34 ms 55276 KB Output is correct
3 Correct 36 ms 55404 KB Output is correct
4 Correct 34 ms 55276 KB Output is correct
5 Correct 35 ms 55276 KB Output is correct
6 Correct 34 ms 55276 KB Output is correct
7 Correct 34 ms 55276 KB Output is correct
8 Correct 34 ms 55276 KB Output is correct
9 Correct 34 ms 55276 KB Output is correct
10 Correct 35 ms 55276 KB Output is correct
11 Correct 34 ms 55276 KB Output is correct
12 Correct 34 ms 55276 KB Output is correct
13 Correct 34 ms 55276 KB Output is correct
14 Correct 34 ms 55276 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 35 ms 55276 KB Output is correct
17 Correct 41 ms 55660 KB Output is correct
18 Correct 39 ms 55788 KB Output is correct
19 Correct 40 ms 55660 KB Output is correct
20 Correct 40 ms 55532 KB Output is correct
21 Correct 40 ms 55660 KB Output is correct
22 Correct 41 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 35 ms 55276 KB Output is correct
2 Correct 34 ms 55276 KB Output is correct
3 Correct 36 ms 55404 KB Output is correct
4 Correct 34 ms 55276 KB Output is correct
5 Correct 35 ms 55276 KB Output is correct
6 Correct 34 ms 55276 KB Output is correct
7 Correct 34 ms 55276 KB Output is correct
8 Correct 34 ms 55276 KB Output is correct
9 Correct 34 ms 55276 KB Output is correct
10 Correct 35 ms 55276 KB Output is correct
11 Correct 34 ms 55276 KB Output is correct
12 Correct 34 ms 55276 KB Output is correct
13 Correct 34 ms 55276 KB Output is correct
14 Correct 34 ms 55276 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 35 ms 55276 KB Output is correct
17 Correct 41 ms 55660 KB Output is correct
18 Correct 39 ms 55788 KB Output is correct
19 Correct 40 ms 55660 KB Output is correct
20 Correct 40 ms 55532 KB Output is correct
21 Correct 40 ms 55660 KB Output is correct
22 Correct 41 ms 55660 KB Output is correct
23 Correct 39 ms 55532 KB Output is correct
24 Correct 468 ms 82104 KB Output is correct
25 Correct 468 ms 80596 KB Output is correct
26 Correct 484 ms 81884 KB Output is correct
27 Correct 489 ms 81900 KB Output is correct
28 Correct 621 ms 83292 KB Output is correct
29 Correct 573 ms 83540 KB Output is correct
30 Correct 863 ms 85612 KB Output is correct
31 Correct 305 ms 73296 KB Output is correct
32 Correct 288 ms 72940 KB Output is correct
33 Correct 512 ms 79340 KB Output is correct
34 Correct 761 ms 84580 KB Output is correct
35 Correct 819 ms 87020 KB Output is correct
36 Correct 829 ms 86928 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 55276 KB Output is correct
2 Correct 34 ms 55276 KB Output is correct
3 Correct 36 ms 55404 KB Output is correct
4 Correct 34 ms 55276 KB Output is correct
5 Correct 35 ms 55276 KB Output is correct
6 Correct 34 ms 55276 KB Output is correct
7 Correct 34 ms 55276 KB Output is correct
8 Correct 34 ms 55276 KB Output is correct
9 Correct 34 ms 55276 KB Output is correct
10 Correct 35 ms 55276 KB Output is correct
11 Correct 34 ms 55276 KB Output is correct
12 Correct 34 ms 55276 KB Output is correct
13 Correct 34 ms 55276 KB Output is correct
14 Correct 34 ms 55276 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 35 ms 55276 KB Output is correct
17 Correct 41 ms 55660 KB Output is correct
18 Correct 39 ms 55788 KB Output is correct
19 Correct 40 ms 55660 KB Output is correct
20 Correct 40 ms 55532 KB Output is correct
21 Correct 40 ms 55660 KB Output is correct
22 Correct 41 ms 55660 KB Output is correct
23 Correct 39 ms 55532 KB Output is correct
24 Correct 468 ms 82104 KB Output is correct
25 Correct 468 ms 80596 KB Output is correct
26 Correct 484 ms 81884 KB Output is correct
27 Correct 489 ms 81900 KB Output is correct
28 Correct 621 ms 83292 KB Output is correct
29 Correct 573 ms 83540 KB Output is correct
30 Correct 863 ms 85612 KB Output is correct
31 Correct 305 ms 73296 KB Output is correct
32 Correct 288 ms 72940 KB Output is correct
33 Correct 512 ms 79340 KB Output is correct
34 Correct 761 ms 84580 KB Output is correct
35 Correct 819 ms 87020 KB Output is correct
36 Correct 829 ms 86928 KB Output is correct
37 Correct 518 ms 81884 KB Output is correct
38 Correct 528 ms 81772 KB Output is correct
39 Correct 420 ms 83180 KB Output is correct
40 Correct 421 ms 83308 KB Output is correct
41 Correct 34 ms 55276 KB Output is correct
42 Correct 890 ms 85556 KB Output is correct
43 Correct 535 ms 79400 KB Output is correct
44 Correct 797 ms 84188 KB Output is correct
45 Correct 840 ms 85612 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 55276 KB Output is correct
2 Correct 34 ms 55276 KB Output is correct
3 Correct 36 ms 55404 KB Output is correct
4 Correct 34 ms 55276 KB Output is correct
5 Correct 35 ms 55276 KB Output is correct
6 Correct 34 ms 55276 KB Output is correct
7 Correct 34 ms 55276 KB Output is correct
8 Correct 34 ms 55276 KB Output is correct
9 Correct 34 ms 55276 KB Output is correct
10 Correct 35 ms 55276 KB Output is correct
11 Correct 34 ms 55276 KB Output is correct
12 Correct 34 ms 55276 KB Output is correct
13 Correct 34 ms 55276 KB Output is correct
14 Correct 34 ms 55276 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 35 ms 55276 KB Output is correct
17 Correct 41 ms 55660 KB Output is correct
18 Correct 39 ms 55788 KB Output is correct
19 Correct 40 ms 55660 KB Output is correct
20 Correct 40 ms 55532 KB Output is correct
21 Correct 40 ms 55660 KB Output is correct
22 Correct 41 ms 55660 KB Output is correct
23 Correct 39 ms 55532 KB Output is correct
24 Correct 468 ms 82104 KB Output is correct
25 Correct 468 ms 80596 KB Output is correct
26 Correct 484 ms 81884 KB Output is correct
27 Correct 489 ms 81900 KB Output is correct
28 Correct 621 ms 83292 KB Output is correct
29 Correct 573 ms 83540 KB Output is correct
30 Correct 863 ms 85612 KB Output is correct
31 Correct 305 ms 73296 KB Output is correct
32 Correct 288 ms 72940 KB Output is correct
33 Correct 512 ms 79340 KB Output is correct
34 Correct 761 ms 84580 KB Output is correct
35 Correct 819 ms 87020 KB Output is correct
36 Correct 829 ms 86928 KB Output is correct
37 Correct 518 ms 81884 KB Output is correct
38 Correct 528 ms 81772 KB Output is correct
39 Correct 420 ms 83180 KB Output is correct
40 Correct 421 ms 83308 KB Output is correct
41 Correct 34 ms 55276 KB Output is correct
42 Correct 890 ms 85556 KB Output is correct
43 Correct 535 ms 79400 KB Output is correct
44 Correct 797 ms 84188 KB Output is correct
45 Correct 840 ms 85612 KB Output is correct
46 Correct 2435 ms 175908 KB Output is correct
47 Correct 2468 ms 175756 KB Output is correct
48 Correct 1948 ms 183108 KB Output is correct
49 Correct 1945 ms 182248 KB Output is correct
50 Correct 5281 ms 194152 KB Output is correct
51 Correct 2924 ms 159712 KB Output is correct
52 Correct 4162 ms 181988 KB Output is correct
53 Correct 4880 ms 191716 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 81644 KB Output is correct
2 Correct 509 ms 82408 KB Output is correct
3 Correct 599 ms 81620 KB Output is correct
4 Correct 349 ms 76396 KB Output is correct
5 Correct 35 ms 55276 KB Output is correct
6 Correct 510 ms 81636 KB Output is correct
7 Correct 298 ms 68316 KB Output is correct
8 Correct 298 ms 71020 KB Output is correct
9 Correct 600 ms 83796 KB Output is correct
10 Correct 382 ms 83784 KB Output is correct
11 Correct 549 ms 83944 KB Output is correct
12 Correct 35 ms 55276 KB Output is correct
13 Correct 34 ms 55276 KB Output is correct
14 Correct 36 ms 55404 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 35 ms 55276 KB Output is correct
17 Correct 34 ms 55276 KB Output is correct
18 Correct 34 ms 55276 KB Output is correct
19 Correct 34 ms 55276 KB Output is correct
20 Correct 34 ms 55276 KB Output is correct
21 Correct 35 ms 55276 KB Output is correct
22 Correct 34 ms 55276 KB Output is correct
23 Correct 34 ms 55276 KB Output is correct
24 Correct 34 ms 55276 KB Output is correct
25 Correct 34 ms 55276 KB Output is correct
26 Correct 34 ms 55276 KB Output is correct
27 Correct 35 ms 55276 KB Output is correct
28 Correct 41 ms 55660 KB Output is correct
29 Correct 39 ms 55788 KB Output is correct
30 Correct 40 ms 55660 KB Output is correct
31 Correct 40 ms 55532 KB Output is correct
32 Correct 40 ms 55660 KB Output is correct
33 Correct 41 ms 55660 KB Output is correct
34 Correct 39 ms 55532 KB Output is correct
35 Correct 468 ms 82104 KB Output is correct
36 Correct 468 ms 80596 KB Output is correct
37 Correct 484 ms 81884 KB Output is correct
38 Correct 489 ms 81900 KB Output is correct
39 Correct 621 ms 83292 KB Output is correct
40 Correct 573 ms 83540 KB Output is correct
41 Correct 863 ms 85612 KB Output is correct
42 Correct 305 ms 73296 KB Output is correct
43 Correct 288 ms 72940 KB Output is correct
44 Correct 512 ms 79340 KB Output is correct
45 Correct 761 ms 84580 KB Output is correct
46 Correct 819 ms 87020 KB Output is correct
47 Correct 829 ms 86928 KB Output is correct
48 Correct 518 ms 81884 KB Output is correct
49 Correct 528 ms 81772 KB Output is correct
50 Correct 420 ms 83180 KB Output is correct
51 Correct 421 ms 83308 KB Output is correct
52 Correct 34 ms 55276 KB Output is correct
53 Correct 890 ms 85556 KB Output is correct
54 Correct 535 ms 79400 KB Output is correct
55 Correct 797 ms 84188 KB Output is correct
56 Correct 840 ms 85612 KB Output is correct
57 Incorrect 521 ms 79452 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 81644 KB Output is correct
2 Correct 509 ms 82408 KB Output is correct
3 Correct 599 ms 81620 KB Output is correct
4 Correct 349 ms 76396 KB Output is correct
5 Correct 35 ms 55276 KB Output is correct
6 Correct 510 ms 81636 KB Output is correct
7 Correct 298 ms 68316 KB Output is correct
8 Correct 298 ms 71020 KB Output is correct
9 Correct 600 ms 83796 KB Output is correct
10 Correct 382 ms 83784 KB Output is correct
11 Correct 549 ms 83944 KB Output is correct
12 Correct 35 ms 55276 KB Output is correct
13 Correct 34 ms 55276 KB Output is correct
14 Correct 36 ms 55404 KB Output is correct
15 Correct 34 ms 55276 KB Output is correct
16 Correct 35 ms 55276 KB Output is correct
17 Correct 34 ms 55276 KB Output is correct
18 Correct 34 ms 55276 KB Output is correct
19 Correct 34 ms 55276 KB Output is correct
20 Correct 34 ms 55276 KB Output is correct
21 Correct 35 ms 55276 KB Output is correct
22 Correct 34 ms 55276 KB Output is correct
23 Correct 34 ms 55276 KB Output is correct
24 Correct 34 ms 55276 KB Output is correct
25 Correct 34 ms 55276 KB Output is correct
26 Correct 34 ms 55276 KB Output is correct
27 Correct 35 ms 55276 KB Output is correct
28 Correct 41 ms 55660 KB Output is correct
29 Correct 39 ms 55788 KB Output is correct
30 Correct 40 ms 55660 KB Output is correct
31 Correct 40 ms 55532 KB Output is correct
32 Correct 40 ms 55660 KB Output is correct
33 Correct 41 ms 55660 KB Output is correct
34 Correct 39 ms 55532 KB Output is correct
35 Correct 468 ms 82104 KB Output is correct
36 Correct 468 ms 80596 KB Output is correct
37 Correct 484 ms 81884 KB Output is correct
38 Correct 489 ms 81900 KB Output is correct
39 Correct 621 ms 83292 KB Output is correct
40 Correct 573 ms 83540 KB Output is correct
41 Correct 863 ms 85612 KB Output is correct
42 Correct 305 ms 73296 KB Output is correct
43 Correct 288 ms 72940 KB Output is correct
44 Correct 512 ms 79340 KB Output is correct
45 Correct 761 ms 84580 KB Output is correct
46 Correct 819 ms 87020 KB Output is correct
47 Correct 829 ms 86928 KB Output is correct
48 Correct 518 ms 81884 KB Output is correct
49 Correct 528 ms 81772 KB Output is correct
50 Correct 420 ms 83180 KB Output is correct
51 Correct 421 ms 83308 KB Output is correct
52 Correct 34 ms 55276 KB Output is correct
53 Correct 890 ms 85556 KB Output is correct
54 Correct 535 ms 79400 KB Output is correct
55 Correct 797 ms 84188 KB Output is correct
56 Correct 840 ms 85612 KB Output is correct
57 Correct 2435 ms 175908 KB Output is correct
58 Correct 2468 ms 175756 KB Output is correct
59 Correct 1948 ms 183108 KB Output is correct
60 Correct 1945 ms 182248 KB Output is correct
61 Correct 5281 ms 194152 KB Output is correct
62 Correct 2924 ms 159712 KB Output is correct
63 Correct 4162 ms 181988 KB Output is correct
64 Correct 4880 ms 191716 KB Output is correct
65 Incorrect 521 ms 79452 KB Output isn't correct
66 Halted 0 ms 0 KB -