oj.uz

Submission #348878

# Submission time Handle Problem Language Result Execution time Memory
348878 2021-01-16T03:42:48 Z ijxjdjd Two Dishes (JOI19_dishes) C++14
74 / 100
 5345 ms 262204 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, M, 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, M, row[i].back().first+1, query(1, 0, M, 0, row[i].back().first));
            add(1, 0, M, 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 457 ms 81516 KB Output is correct
2 Correct 492 ms 82536 KB Output is correct
3 Correct 434 ms 81388 KB Output is correct
4 Correct 361 ms 76016 KB Output is correct
5 Correct 34 ms 55148 KB Output is correct
6 Correct 445 ms 81636 KB Output is correct
7 Correct 285 ms 68188 KB Output is correct
8 Correct 138 ms 74732 KB Output is correct
9 Correct 445 ms 95956 KB Output is correct
10 Correct 371 ms 88684 KB Output is correct
11 Correct 395 ms 89148 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

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

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 55148 KB Output is correct
2 Correct 32 ms 55208 KB Output is correct
3 Correct 33 ms 55148 KB Output is correct
4 Correct 33 ms 55148 KB Output is correct
5 Correct 33 ms 55148 KB Output is correct
6 Correct 33 ms 55148 KB Output is correct
7 Correct 33 ms 55148 KB Output is correct
8 Correct 33 ms 55148 KB Output is correct
9 Correct 33 ms 55148 KB Output is correct
10 Correct 38 ms 55148 KB Output is correct
11 Correct 33 ms 55148 KB Output is correct
12 Correct 39 ms 55148 KB Output is correct
13 Correct 38 ms 55148 KB Output is correct
14 Correct 33 ms 55148 KB Output is correct
15 Correct 34 ms 55148 KB Output is correct
16 Correct 33 ms 55148 KB Output is correct
17 Correct 36 ms 55532 KB Output is correct
18 Correct 38 ms 55532 KB Output is correct
19 Correct 38 ms 55532 KB Output is correct
20 Correct 36 ms 55532 KB Output is correct
21 Correct 38 ms 55532 KB Output is correct
22 Correct 39 ms 55532 KB Output is correct
23 Correct 37 ms 55532 KB Output is correct
24 Correct 446 ms 90460 KB Output is correct
25 Correct 392 ms 88788 KB Output is correct
26 Correct 463 ms 90516 KB Output is correct
27 Correct 412 ms 90512 KB Output is correct
28 Correct 495 ms 91868 KB Output is correct
29 Correct 419 ms 92724 KB Output is correct
30 Correct 850 ms 94188 KB Output is correct
31 Correct 280 ms 74192 KB Output is correct
32 Correct 128 ms 73068 KB Output is correct
33 Correct 495 ms 87916 KB Output is correct
34 Correct 694 ms 93284 KB Output is correct
35 Correct 786 ms 87916 KB Output is correct
36 Correct 771 ms 87660 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 55148 KB Output is correct
2 Correct 32 ms 55208 KB Output is correct
3 Correct 33 ms 55148 KB Output is correct
4 Correct 33 ms 55148 KB Output is correct
5 Correct 33 ms 55148 KB Output is correct
6 Correct 33 ms 55148 KB Output is correct
7 Correct 33 ms 55148 KB Output is correct
8 Correct 33 ms 55148 KB Output is correct
9 Correct 33 ms 55148 KB Output is correct
10 Correct 38 ms 55148 KB Output is correct
11 Correct 33 ms 55148 KB Output is correct
12 Correct 39 ms 55148 KB Output is correct
13 Correct 38 ms 55148 KB Output is correct
14 Correct 33 ms 55148 KB Output is correct
15 Correct 34 ms 55148 KB Output is correct
16 Correct 33 ms 55148 KB Output is correct
17 Correct 36 ms 55532 KB Output is correct
18 Correct 38 ms 55532 KB Output is correct
19 Correct 38 ms 55532 KB Output is correct
20 Correct 36 ms 55532 KB Output is correct
21 Correct 38 ms 55532 KB Output is correct
22 Correct 39 ms 55532 KB Output is correct
23 Correct 37 ms 55532 KB Output is correct
24 Correct 446 ms 90460 KB Output is correct
25 Correct 392 ms 88788 KB Output is correct
26 Correct 463 ms 90516 KB Output is correct
27 Correct 412 ms 90512 KB Output is correct
28 Correct 495 ms 91868 KB Output is correct
29 Correct 419 ms 92724 KB Output is correct
30 Correct 850 ms 94188 KB Output is correct
31 Correct 280 ms 74192 KB Output is correct
32 Correct 128 ms 73068 KB Output is correct
33 Correct 495 ms 87916 KB Output is correct
34 Correct 694 ms 93284 KB Output is correct
35 Correct 786 ms 87916 KB Output is correct
36 Correct 771 ms 87660 KB Output is correct
37 Correct 487 ms 93532 KB Output is correct
38 Correct 433 ms 93380 KB Output is correct
39 Correct 402 ms 92524 KB Output is correct
40 Correct 401 ms 92396 KB Output is correct
41 Correct 35 ms 55148 KB Output is correct
42 Correct 861 ms 97204 KB Output is correct
43 Correct 580 ms 90732 KB Output is correct
44 Correct 728 ms 96100 KB Output is correct
45 Correct 808 ms 90996 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 55148 KB Output is correct
2 Correct 32 ms 55208 KB Output is correct
3 Correct 33 ms 55148 KB Output is correct
4 Correct 33 ms 55148 KB Output is correct
5 Correct 33 ms 55148 KB Output is correct
6 Correct 33 ms 55148 KB Output is correct
7 Correct 33 ms 55148 KB Output is correct
8 Correct 33 ms 55148 KB Output is correct
9 Correct 33 ms 55148 KB Output is correct
10 Correct 38 ms 55148 KB Output is correct
11 Correct 33 ms 55148 KB Output is correct
12 Correct 39 ms 55148 KB Output is correct
13 Correct 38 ms 55148 KB Output is correct
14 Correct 33 ms 55148 KB Output is correct
15 Correct 34 ms 55148 KB Output is correct
16 Correct 33 ms 55148 KB Output is correct
17 Correct 36 ms 55532 KB Output is correct
18 Correct 38 ms 55532 KB Output is correct
19 Correct 38 ms 55532 KB Output is correct
20 Correct 36 ms 55532 KB Output is correct
21 Correct 38 ms 55532 KB Output is correct
22 Correct 39 ms 55532 KB Output is correct
23 Correct 37 ms 55532 KB Output is correct
24 Correct 446 ms 90460 KB Output is correct
25 Correct 392 ms 88788 KB Output is correct
26 Correct 463 ms 90516 KB Output is correct
27 Correct 412 ms 90512 KB Output is correct
28 Correct 495 ms 91868 KB Output is correct
29 Correct 419 ms 92724 KB Output is correct
30 Correct 850 ms 94188 KB Output is correct
31 Correct 280 ms 74192 KB Output is correct
32 Correct 128 ms 73068 KB Output is correct
33 Correct 495 ms 87916 KB Output is correct
34 Correct 694 ms 93284 KB Output is correct
35 Correct 786 ms 87916 KB Output is correct
36 Correct 771 ms 87660 KB Output is correct
37 Correct 487 ms 93532 KB Output is correct
38 Correct 433 ms 93380 KB Output is correct
39 Correct 402 ms 92524 KB Output is correct
40 Correct 401 ms 92396 KB Output is correct
41 Correct 35 ms 55148 KB Output is correct
42 Correct 861 ms 97204 KB Output is correct
43 Correct 580 ms 90732 KB Output is correct
44 Correct 728 ms 96100 KB Output is correct
45 Correct 808 ms 90996 KB Output is correct
46 Correct 2466 ms 243700 KB Output is correct
47 Correct 2159 ms 243284 KB Output is correct
48 Correct 2029 ms 236796 KB Output is correct
49 Correct 1968 ms 237576 KB Output is correct
50 Correct 5345 ms 262204 KB Output is correct
51 Correct 2950 ms 226512 KB Output is correct
52 Correct 3963 ms 250020 KB Output is correct
53 Correct 4981 ms 230264 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 81516 KB Output is correct
2 Correct 492 ms 82536 KB Output is correct
3 Correct 434 ms 81388 KB Output is correct
4 Correct 361 ms 76016 KB Output is correct
5 Correct 34 ms 55148 KB Output is correct
6 Correct 445 ms 81636 KB Output is correct
7 Correct 285 ms 68188 KB Output is correct
8 Correct 138 ms 74732 KB Output is correct
9 Correct 445 ms 95956 KB Output is correct
10 Correct 371 ms 88684 KB Output is correct
11 Correct 395 ms 89148 KB Output is correct
12 Correct 33 ms 55148 KB Output is correct
13 Correct 32 ms 55208 KB Output is correct
14 Correct 33 ms 55148 KB Output is correct
15 Correct 33 ms 55148 KB Output is correct
16 Correct 33 ms 55148 KB Output is correct
17 Correct 33 ms 55148 KB Output is correct
18 Correct 33 ms 55148 KB Output is correct
19 Correct 33 ms 55148 KB Output is correct
20 Correct 33 ms 55148 KB Output is correct
21 Correct 38 ms 55148 KB Output is correct
22 Correct 33 ms 55148 KB Output is correct
23 Correct 39 ms 55148 KB Output is correct
24 Correct 38 ms 55148 KB Output is correct
25 Correct 33 ms 55148 KB Output is correct
26 Correct 34 ms 55148 KB Output is correct
27 Correct 33 ms 55148 KB Output is correct
28 Correct 36 ms 55532 KB Output is correct
29 Correct 38 ms 55532 KB Output is correct
30 Correct 38 ms 55532 KB Output is correct
31 Correct 36 ms 55532 KB Output is correct
32 Correct 38 ms 55532 KB Output is correct
33 Correct 39 ms 55532 KB Output is correct
34 Correct 37 ms 55532 KB Output is correct
35 Correct 446 ms 90460 KB Output is correct
36 Correct 392 ms 88788 KB Output is correct
37 Correct 463 ms 90516 KB Output is correct
38 Correct 412 ms 90512 KB Output is correct
39 Correct 495 ms 91868 KB Output is correct
40 Correct 419 ms 92724 KB Output is correct
41 Correct 850 ms 94188 KB Output is correct
42 Correct 280 ms 74192 KB Output is correct
43 Correct 128 ms 73068 KB Output is correct
44 Correct 495 ms 87916 KB Output is correct
45 Correct 694 ms 93284 KB Output is correct
46 Correct 786 ms 87916 KB Output is correct
47 Correct 771 ms 87660 KB Output is correct
48 Correct 487 ms 93532 KB Output is correct
49 Correct 433 ms 93380 KB Output is correct
50 Correct 402 ms 92524 KB Output is correct
51 Correct 401 ms 92396 KB Output is correct
52 Correct 35 ms 55148 KB Output is correct
53 Correct 861 ms 97204 KB Output is correct
54 Correct 580 ms 90732 KB Output is correct
55 Correct 728 ms 96100 KB Output is correct
56 Correct 808 ms 90996 KB Output is correct
57 Incorrect 498 ms 93968 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 81516 KB Output is correct
2 Correct 492 ms 82536 KB Output is correct
3 Correct 434 ms 81388 KB Output is correct
4 Correct 361 ms 76016 KB Output is correct
5 Correct 34 ms 55148 KB Output is correct
6 Correct 445 ms 81636 KB Output is correct
7 Correct 285 ms 68188 KB Output is correct
8 Correct 138 ms 74732 KB Output is correct
9 Correct 445 ms 95956 KB Output is correct
10 Correct 371 ms 88684 KB Output is correct
11 Correct 395 ms 89148 KB Output is correct
12 Correct 33 ms 55148 KB Output is correct
13 Correct 32 ms 55208 KB Output is correct
14 Correct 33 ms 55148 KB Output is correct
15 Correct 33 ms 55148 KB Output is correct
16 Correct 33 ms 55148 KB Output is correct
17 Correct 33 ms 55148 KB Output is correct
18 Correct 33 ms 55148 KB Output is correct
19 Correct 33 ms 55148 KB Output is correct
20 Correct 33 ms 55148 KB Output is correct
21 Correct 38 ms 55148 KB Output is correct
22 Correct 33 ms 55148 KB Output is correct
23 Correct 39 ms 55148 KB Output is correct
24 Correct 38 ms 55148 KB Output is correct
25 Correct 33 ms 55148 KB Output is correct
26 Correct 34 ms 55148 KB Output is correct
27 Correct 33 ms 55148 KB Output is correct
28 Correct 36 ms 55532 KB Output is correct
29 Correct 38 ms 55532 KB Output is correct
30 Correct 38 ms 55532 KB Output is correct
31 Correct 36 ms 55532 KB Output is correct
32 Correct 38 ms 55532 KB Output is correct
33 Correct 39 ms 55532 KB Output is correct
34 Correct 37 ms 55532 KB Output is correct
35 Correct 446 ms 90460 KB Output is correct
36 Correct 392 ms 88788 KB Output is correct
37 Correct 463 ms 90516 KB Output is correct
38 Correct 412 ms 90512 KB Output is correct
39 Correct 495 ms 91868 KB Output is correct
40 Correct 419 ms 92724 KB Output is correct
41 Correct 850 ms 94188 KB Output is correct
42 Correct 280 ms 74192 KB Output is correct
43 Correct 128 ms 73068 KB Output is correct
44 Correct 495 ms 87916 KB Output is correct
45 Correct 694 ms 93284 KB Output is correct
46 Correct 786 ms 87916 KB Output is correct
47 Correct 771 ms 87660 KB Output is correct
48 Correct 487 ms 93532 KB Output is correct
49 Correct 433 ms 93380 KB Output is correct
50 Correct 402 ms 92524 KB Output is correct
51 Correct 401 ms 92396 KB Output is correct
52 Correct 35 ms 55148 KB Output is correct
53 Correct 861 ms 97204 KB Output is correct
54 Correct 580 ms 90732 KB Output is correct
55 Correct 728 ms 96100 KB Output is correct
56 Correct 808 ms 90996 KB Output is correct
57 Correct 2466 ms 243700 KB Output is correct
58 Correct 2159 ms 243284 KB Output is correct
59 Correct 2029 ms 236796 KB Output is correct
60 Correct 1968 ms 237576 KB Output is correct
61 Correct 5345 ms 262204 KB Output is correct
62 Correct 2950 ms 226512 KB Output is correct
63 Correct 3963 ms 250020 KB Output is correct
64 Correct 4981 ms 230264 KB Output is correct
65 Incorrect 498 ms 93968 KB Output isn't correct
66 Halted 0 ms 0 KB -