oj.uz

Submission #123282

# Submission time Handle Problem Language Result Execution time Memory
123282 2019-07-01T05:42:43 Z 윤교준(#3020) Two Dishes (JOI19_dishes) C++14
65 / 100
 2982 ms 57624 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define rb(x) ((x)&(-(x)))
using namespace std;
typedef long long ll;

const bool debug = 0;

const int MAXN = 200055;
const int MAXM = 200055;

struct BIT {
	ll d[MAXN];

	void upd(int x, ll r) {
		for(x += 5; x < MAXN; x += rb(x))
			d[x] += r;
	}
	ll get(int x) {
		ll r = 0; for(x += 5; x; x -= rb(x))
			r += d[x];
		return r;
	}
	ll get(int s, int e) { return s > e ? 0 : get(e) - get(s-1); }
} bit;

struct SEG {
	ll ds[MAXN*3];
	bitset<MAXN*3> dz;

	void prop(int i, int s, int e) {
		if(dz[i]) {
			ds[i] = 0;
			if(s != e) dz[i<<1] = dz[i<<1|1] = true;
			dz[i] = false;
			return;
		}
		if(s == e) return;
		ds[i] = 0;
		if(!dz[i<<1]) ds[i] += ds[i<<1];
		if(!dz[i<<1|1]) ds[i] += ds[i<<1|1];
	}
	void updz(int i, int s, int e, int p, int q) {
		prop(i, s, e); if(q < p || e < p || q < s) return;
		if(p <= s && e <= q) {
			dz[i] = true;
			prop(i, s, e);
			return;
		}
		int m = (s+e) >> 1;
		updz(i<<1, s, m, p, q);
		updz(i<<1|1, m+1, e, p, q);
		ds[i] = ds[i<<1] + ds[i<<1|1];
	}
	void updp(int i, int s, int e, int x, ll r) {
		prop(i, s, e); if(x < s || e < x) return;
		if(s == e) {
			ds[i] = r;
			return;
		}
		int m = (s+e) >> 1;
		updp(i<<1, s, m, x, r);
		updp(i<<1|1, m+1, e, x, r);
		ds[i] = ds[i<<1] + ds[i<<1|1];
	}
	void upddx(int i, int s, int e, int x, ll r) {
		prop(i, s, e); if(x < s || e < x) return;
		if(s == e) {
			ds[i] += r;
			return;
		}
		int m = (s+e) >> 1;
		upddx(i<<1, s, m, x, r);
		upddx(i<<1|1, m+1, e, x, r);
		ds[i] = ds[i<<1] + ds[i<<1|1];
	}
	ll get(int i, int s, int e, int p, int q) {
		prop(i, s, e); if(q < p || e < p || q < s) return 0;
		if(p <= s && e <= q) return ds[i];
		int m = (s+e) >> 1;
		ll ret = get(i<<1, s, m, p, q) + get(i<<1|1, m+1, e, p, q);
		ds[i] = ds[i<<1] + ds[i<<1|1];
		return ret;
	}
	ll get(int i, int s, int e, int x) { return get(1, s, e, x, x); }
} seg;

vector<int> PopEV[MAXM];

ll SA[MAXN], SB[MAXM];
int FI[MAXN], GI[MAXM];

ll C[MAXN], D[MAXM];
int A[MAXN], B[MAXM];
int E[MAXN], F[MAXM];

ll Delta;
int N, M;

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 1; i <= N; i++)
		cin >> A[i] >> C[i] >> E[i];
	for(int i = 1; i <= M; i++)
		cin >> B[i] >> D[i] >> F[i];
	
	for(int i = 1; i <= N; i++) SA[i] = SA[i-1] + A[i];
	for(int i = 1; i <= M; i++) SB[i] = SB[i-1] + B[i];

	for(int i = 1; i <= N; i++)
		FI[i] = int(upper_bound(SB, SB+M+1, C[i]-SA[i])-SB) - 1;
	for(int i = 1; i <= M; i++)
		GI[i] = int(upper_bound(SA, SA+N+1, D[i]-SB[i])-SA) - 1;
	
	for(int i = 1; i <= N; i++) PopEV[FI[i]+1].eb(i);
	for(int i = 1; i <= N; i++)
		if(0 <= FI[i]) bit.upd(i, E[i]);
	
	if(debug) {
		printf("N=%d, M=%d\n", N, M);
		for(int i = 1; i <= N; i++) printf("%d ", FI[i]);
		puts("");
		for(int i = 1; i <= M; i++) printf("%d ", GI[i]);
		puts("");
	}
	
	for(int j = 1; j <= M; j++) {
		for(int i : PopEV[j]) {
			bit.upd(i, -E[i]);
			seg.upddx(1, 1, N, i, E[i]);
			if(debug) {
				printf("j=%d, pop %d %d\n", j, i, E[i]);
			}
		}

		if(0 <= GI[j]) {
			Delta += F[j];
			int s = GI[j]+1, e = N+1; for(int m; s < e;) {
				m = (s+e) >> 1;
				if(seg.get(1, 1, N, GI[j]+1, m) < F[j]) s = m+1;
				else e = m;
			}
			ll t = seg.get(1, 1, N, GI[j]+1, s-1);
			if(debug) {
				printf("j=%d, GI=%d, s=%d, t=%lld / %lld\n", j, GI[j], s, t, seg.get(1, 1, N, GI[j]+1, s));
			}
			seg.updz(1, 1, N, GI[j]+1, s-1);
			if(s <= N) seg.upddx(1, 1, N, s, t-F[j]);
		}

		if(debug) {
			printf("j=%d / %lld\n", j, Delta);
			for(int i = 1; i <= N; i++) printf("%lld ", bit.get(i, i));
			puts("");
			for(int i = 1; i <= N; i++) printf("%lld ", seg.get(1, 1, N, i));
			puts("");
		}
	}

	cout << bit.get(1, N) + seg.get(1, 1, N, 1, N) + Delta << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2289 ms 25900 KB Output is correct
2 Correct 1826 ms 25236 KB Output is correct
3 Correct 240 ms 19248 KB Output is correct
4 Correct 1668 ms 25716 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 1600 ms 36856 KB Output is correct
7 Correct 115 ms 17528 KB Output is correct
8 Correct 123 ms 20192 KB Output is correct
9 Correct 246 ms 33008 KB Output is correct
10 Correct 2154 ms 35488 KB Output is correct
11 Correct 176 ms 26352 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5240 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Correct 6 ms 5240 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 6 ms 5240 KB Output is correct
7 Correct 6 ms 5240 KB Output is correct
8 Correct 6 ms 5240 KB Output is correct
9 Correct 6 ms 5240 KB Output is correct
10 Correct 6 ms 5240 KB Output is correct
11 Correct 6 ms 5240 KB Output is correct
12 Correct 6 ms 5240 KB Output is correct
13 Correct 10 ms 5240 KB Output is correct
14 Correct 6 ms 5240 KB Output is correct
15 Correct 6 ms 5240 KB Output is correct
16 Correct 6 ms 5240 KB Output is correct
17 Correct 8 ms 5496 KB Output is correct
18 Correct 12 ms 5496 KB Output is correct
19 Correct 19 ms 5496 KB Output is correct
20 Correct 14 ms 5496 KB Output is correct
21 Correct 15 ms 5496 KB Output is correct
22 Correct 19 ms 5496 KB Output is correct
23 Correct 19 ms 5368 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5240 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Correct 6 ms 5240 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 6 ms 5240 KB Output is correct
7 Correct 6 ms 5240 KB Output is correct
8 Correct 6 ms 5240 KB Output is correct
9 Correct 6 ms 5240 KB Output is correct
10 Correct 6 ms 5240 KB Output is correct
11 Correct 6 ms 5240 KB Output is correct
12 Correct 6 ms 5240 KB Output is correct
13 Correct 10 ms 5240 KB Output is correct
14 Correct 6 ms 5240 KB Output is correct
15 Correct 6 ms 5240 KB Output is correct
16 Correct 6 ms 5240 KB Output is correct
17 Correct 8 ms 5496 KB Output is correct
18 Correct 12 ms 5496 KB Output is correct
19 Correct 19 ms 5496 KB Output is correct
20 Correct 14 ms 5496 KB Output is correct
21 Correct 15 ms 5496 KB Output is correct
22 Correct 19 ms 5496 KB Output is correct
23 Correct 19 ms 5368 KB Output is correct
24 Correct 279 ms 33256 KB Output is correct
25 Correct 1476 ms 29568 KB Output is correct
26 Correct 300 ms 38660 KB Output is correct
27 Correct 2306 ms 33576 KB Output is correct
28 Correct 945 ms 34552 KB Output is correct
29 Correct 215 ms 29932 KB Output is correct
30 Correct 2881 ms 36600 KB Output is correct
31 Correct 103 ms 15864 KB Output is correct
32 Correct 143 ms 22500 KB Output is correct
33 Correct 1607 ms 34780 KB Output is correct
34 Correct 2212 ms 34704 KB Output is correct
35 Correct 2924 ms 29980 KB Output is correct
36 Correct 2819 ms 29988 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5240 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Correct 6 ms 5240 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 6 ms 5240 KB Output is correct
7 Correct 6 ms 5240 KB Output is correct
8 Correct 6 ms 5240 KB Output is correct
9 Correct 6 ms 5240 KB Output is correct
10 Correct 6 ms 5240 KB Output is correct
11 Correct 6 ms 5240 KB Output is correct
12 Correct 6 ms 5240 KB Output is correct
13 Correct 10 ms 5240 KB Output is correct
14 Correct 6 ms 5240 KB Output is correct
15 Correct 6 ms 5240 KB Output is correct
16 Correct 6 ms 5240 KB Output is correct
17 Correct 8 ms 5496 KB Output is correct
18 Correct 12 ms 5496 KB Output is correct
19 Correct 19 ms 5496 KB Output is correct
20 Correct 14 ms 5496 KB Output is correct
21 Correct 15 ms 5496 KB Output is correct
22 Correct 19 ms 5496 KB Output is correct
23 Correct 19 ms 5368 KB Output is correct
24 Correct 279 ms 33256 KB Output is correct
25 Correct 1476 ms 29568 KB Output is correct
26 Correct 300 ms 38660 KB Output is correct
27 Correct 2306 ms 33576 KB Output is correct
28 Correct 945 ms 34552 KB Output is correct
29 Correct 215 ms 29932 KB Output is correct
30 Correct 2881 ms 36600 KB Output is correct
31 Correct 103 ms 15864 KB Output is correct
32 Correct 143 ms 22500 KB Output is correct
33 Correct 1607 ms 34780 KB Output is correct
34 Correct 2212 ms 34704 KB Output is correct
35 Correct 2924 ms 29980 KB Output is correct
36 Correct 2819 ms 29988 KB Output is correct
37 Correct 334 ms 41652 KB Output is correct
38 Correct 2342 ms 36520 KB Output is correct
39 Correct 2692 ms 39012 KB Output is correct
40 Correct 2067 ms 39224 KB Output is correct
41 Correct 6 ms 5240 KB Output is correct
42 Correct 2982 ms 39420 KB Output is correct
43 Correct 1593 ms 37764 KB Output is correct
44 Correct 2145 ms 37588 KB Output is correct
45 Correct 2961 ms 33120 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5240 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Correct 6 ms 5240 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 6 ms 5240 KB Output is correct
7 Correct 6 ms 5240 KB Output is correct
8 Correct 6 ms 5240 KB Output is correct
9 Correct 6 ms 5240 KB Output is correct
10 Correct 6 ms 5240 KB Output is correct
11 Correct 6 ms 5240 KB Output is correct
12 Correct 6 ms 5240 KB Output is correct
13 Correct 10 ms 5240 KB Output is correct
14 Correct 6 ms 5240 KB Output is correct
15 Correct 6 ms 5240 KB Output is correct
16 Correct 6 ms 5240 KB Output is correct
17 Correct 8 ms 5496 KB Output is correct
18 Correct 12 ms 5496 KB Output is correct
19 Correct 19 ms 5496 KB Output is correct
20 Correct 14 ms 5496 KB Output is correct
21 Correct 15 ms 5496 KB Output is correct
22 Correct 19 ms 5496 KB Output is correct
23 Correct 19 ms 5368 KB Output is correct
24 Correct 279 ms 33256 KB Output is correct
25 Correct 1476 ms 29568 KB Output is correct
26 Correct 300 ms 38660 KB Output is correct
27 Correct 2306 ms 33576 KB Output is correct
28 Correct 945 ms 34552 KB Output is correct
29 Correct 215 ms 29932 KB Output is correct
30 Correct 2881 ms 36600 KB Output is correct
31 Correct 103 ms 15864 KB Output is correct
32 Correct 143 ms 22500 KB Output is correct
33 Correct 1607 ms 34780 KB Output is correct
34 Correct 2212 ms 34704 KB Output is correct
35 Correct 2924 ms 29980 KB Output is correct
36 Correct 2819 ms 29988 KB Output is correct
37 Correct 334 ms 41652 KB Output is correct
38 Correct 2342 ms 36520 KB Output is correct
39 Correct 2692 ms 39012 KB Output is correct
40 Correct 2067 ms 39224 KB Output is correct
41 Correct 6 ms 5240 KB Output is correct
42 Correct 2982 ms 39420 KB Output is correct
43 Correct 1593 ms 37764 KB Output is correct
44 Correct 2145 ms 37588 KB Output is correct
45 Correct 2961 ms 33120 KB Output is correct
46 Runtime error 1128 ms 57624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
47 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2289 ms 25900 KB Output is correct
2 Correct 1826 ms 25236 KB Output is correct
3 Correct 240 ms 19248 KB Output is correct
4 Correct 1668 ms 25716 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 1600 ms 36856 KB Output is correct
7 Correct 115 ms 17528 KB Output is correct
8 Correct 123 ms 20192 KB Output is correct
9 Correct 246 ms 33008 KB Output is correct
10 Correct 2154 ms 35488 KB Output is correct
11 Correct 176 ms 26352 KB Output is correct
12 Correct 6 ms 5240 KB Output is correct
13 Correct 6 ms 5240 KB Output is correct
14 Correct 6 ms 5240 KB Output is correct
15 Correct 6 ms 5240 KB Output is correct
16 Correct 6 ms 5240 KB Output is correct
17 Correct 6 ms 5240 KB Output is correct
18 Correct 6 ms 5240 KB Output is correct
19 Correct 6 ms 5240 KB Output is correct
20 Correct 6 ms 5240 KB Output is correct
21 Correct 6 ms 5240 KB Output is correct
22 Correct 6 ms 5240 KB Output is correct
23 Correct 6 ms 5240 KB Output is correct
24 Correct 10 ms 5240 KB Output is correct
25 Correct 6 ms 5240 KB Output is correct
26 Correct 6 ms 5240 KB Output is correct
27 Correct 6 ms 5240 KB Output is correct
28 Correct 8 ms 5496 KB Output is correct
29 Correct 12 ms 5496 KB Output is correct
30 Correct 19 ms 5496 KB Output is correct
31 Correct 14 ms 5496 KB Output is correct
32 Correct 15 ms 5496 KB Output is correct
33 Correct 19 ms 5496 KB Output is correct
34 Correct 19 ms 5368 KB Output is correct
35 Correct 279 ms 33256 KB Output is correct
36 Correct 1476 ms 29568 KB Output is correct
37 Correct 300 ms 38660 KB Output is correct
38 Correct 2306 ms 33576 KB Output is correct
39 Correct 945 ms 34552 KB Output is correct
40 Correct 215 ms 29932 KB Output is correct
41 Correct 2881 ms 36600 KB Output is correct
42 Correct 103 ms 15864 KB Output is correct
43 Correct 143 ms 22500 KB Output is correct
44 Correct 1607 ms 34780 KB Output is correct
45 Correct 2212 ms 34704 KB Output is correct
46 Correct 2924 ms 29980 KB Output is correct
47 Correct 2819 ms 29988 KB Output is correct
48 Correct 334 ms 41652 KB Output is correct
49 Correct 2342 ms 36520 KB Output is correct
50 Correct 2692 ms 39012 KB Output is correct
51 Correct 2067 ms 39224 KB Output is correct
52 Correct 6 ms 5240 KB Output is correct
53 Correct 2982 ms 39420 KB Output is correct
54 Correct 1593 ms 37764 KB Output is correct
55 Correct 2145 ms 37588 KB Output is correct
56 Correct 2961 ms 33120 KB Output is correct
57 Incorrect 346 ms 42272 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2289 ms 25900 KB Output is correct
2 Correct 1826 ms 25236 KB Output is correct
3 Correct 240 ms 19248 KB Output is correct
4 Correct 1668 ms 25716 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Correct 1600 ms 36856 KB Output is correct
7 Correct 115 ms 17528 KB Output is correct
8 Correct 123 ms 20192 KB Output is correct
9 Correct 246 ms 33008 KB Output is correct
10 Correct 2154 ms 35488 KB Output is correct
11 Correct 176 ms 26352 KB Output is correct
12 Correct 6 ms 5240 KB Output is correct
13 Correct 6 ms 5240 KB Output is correct
14 Correct 6 ms 5240 KB Output is correct
15 Correct 6 ms 5240 KB Output is correct
16 Correct 6 ms 5240 KB Output is correct
17 Correct 6 ms 5240 KB Output is correct
18 Correct 6 ms 5240 KB Output is correct
19 Correct 6 ms 5240 KB Output is correct
20 Correct 6 ms 5240 KB Output is correct
21 Correct 6 ms 5240 KB Output is correct
22 Correct 6 ms 5240 KB Output is correct
23 Correct 6 ms 5240 KB Output is correct
24 Correct 10 ms 5240 KB Output is correct
25 Correct 6 ms 5240 KB Output is correct
26 Correct 6 ms 5240 KB Output is correct
27 Correct 6 ms 5240 KB Output is correct
28 Correct 8 ms 5496 KB Output is correct
29 Correct 12 ms 5496 KB Output is correct
30 Correct 19 ms 5496 KB Output is correct
31 Correct 14 ms 5496 KB Output is correct
32 Correct 15 ms 5496 KB Output is correct
33 Correct 19 ms 5496 KB Output is correct
34 Correct 19 ms 5368 KB Output is correct
35 Correct 279 ms 33256 KB Output is correct
36 Correct 1476 ms 29568 KB Output is correct
37 Correct 300 ms 38660 KB Output is correct
38 Correct 2306 ms 33576 KB Output is correct
39 Correct 945 ms 34552 KB Output is correct
40 Correct 215 ms 29932 KB Output is correct
41 Correct 2881 ms 36600 KB Output is correct
42 Correct 103 ms 15864 KB Output is correct
43 Correct 143 ms 22500 KB Output is correct
44 Correct 1607 ms 34780 KB Output is correct
45 Correct 2212 ms 34704 KB Output is correct
46 Correct 2924 ms 29980 KB Output is correct
47 Correct 2819 ms 29988 KB Output is correct
48 Correct 334 ms 41652 KB Output is correct
49 Correct 2342 ms 36520 KB Output is correct
50 Correct 2692 ms 39012 KB Output is correct
51 Correct 2067 ms 39224 KB Output is correct
52 Correct 6 ms 5240 KB Output is correct
53 Correct 2982 ms 39420 KB Output is correct
54 Correct 1593 ms 37764 KB Output is correct
55 Correct 2145 ms 37588 KB Output is correct
56 Correct 2961 ms 33120 KB Output is correct
57 Runtime error 1128 ms 57624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
58 Halted 0 ms 0 KB -