Submission #103853

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
103853	2019-04-03T03:04:35 Z	mzhao	Two Dishes (JOI19_dishes)	C++11	49 / 100	869 ms	70264 KB

dishes

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif

#define MN 1000009
#define ll long long
#define x first
#define y second

ll N, M, A[MN], TA[MN], VA[MN], SA[MN], B[MN], TB[MN], VB[MN], SB[MN];
ll sa[MN], sb[MN], ma[MN], mb[MN];
vector<pair<ll, bool>> p[MN]; // (y value, is dish A?)

ll findm(ll a[], ll len, ll x) { // index of last element <= x
	ll l = -1, h = len;
	while (l < h-1) {
		ll m = (l+h)/2;
		if (a[m] > x) h = m;
		else l = m;
	}
	return l;
}

ll t[4*MN], l[4*MN];

void push(ll n, ll a, ll b) {
	t[n] += l[n];
	if (a < b-1) {
		l[2*n] += l[n];
		l[2*n+1] += l[n];
	}
	l[n] = 0;
}

ll query(ll n, ll a, ll b, ll x, ll y) {
	if (l[n]) push(n, a, b);
	if (b <= x || y <= a) return -1e16;
	if (x <= a && b <= y) return t[n];
	return max(query(2*n, a, (a+b)/2, x, y), query(2*n+1, (a+b)/2, b, x, y));
}

ll update(ll n, ll a, ll b, ll x, ll y, ll v) {
	if (l[n]) push(n, a, b);
	if (b <= x || y <= a) return t[n];
	if (x <= a && b <= y) {
		l[n] += v;
		push(n, a, b);
	} else {
		t[n] = max(update(2*n, a, (a+b)/2, x, y, v), update(2*n+1, (a+b)/2, b, x, y, v));
	}
	return t[n];
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> TA[i] >> VA[i];
		sa[i] = sa[i-1]+A[i];
		assert(VA[i] == 1);
	}
	for (int i = 1; i <= M; i++) {
		cin >> B[i] >> TB[i] >> VB[i];
		sb[i] = sb[i-1]+B[i];
		assert(VB[i] == 1);
	}
	for (int i = 1; i <= N; i++) {
		ma[i] = findm(sb, M+1, TA[i]-sa[i]);
		p[i].push_back({ma[i], 1});
	}
	for (int i = 1; i <= M; i++) {
		mb[i] = findm(sa, N+1, TB[i]-sb[i]);
		if (mb[i] >= 0)
			p[mb[i]].push_back({i, 0});
	}
	for (int i = 1; i <= N; i++) D("%lld ", ma[i]);
	D("\n");
	for (int i = 1; i <= M; i++) D("%lld ", mb[i]);
	D("\n");
	for (int i = 0; i <= N; i++) {
		for (pair<ll, bool> j : p[i]) {
			if (j.y) {
				update(1, 0, M+1, 0, j.x+1, 1);
			} else {
				ll best = query(1, 0, M+1, 0, j.x+1);
				ll cur = query(1, 0, M+1, j.x, j.x+1);
				update(1, 0, M+1, j.x, j.x+1, best-cur);
				update(1, 0, M+1, j.x, M+1, 1);
			}
		}
	}
	cout << query(1, 0, M+1, 0, M+1) << "\n";
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	58 ms	47608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	24056 KB	Output is correct
2	Correct	29 ms	23936 KB	Output is correct
3	Correct	25 ms	23928 KB	Output is correct
4	Correct	25 ms	23928 KB	Output is correct
5	Correct	26 ms	23936 KB	Output is correct
6	Correct	24 ms	23908 KB	Output is correct
7	Correct	26 ms	23952 KB	Output is correct
8	Correct	25 ms	23928 KB	Output is correct
9	Correct	27 ms	23960 KB	Output is correct
10	Correct	24 ms	23996 KB	Output is correct
11	Correct	25 ms	23928 KB	Output is correct
12	Correct	27 ms	23936 KB	Output is correct
13	Correct	25 ms	23928 KB	Output is correct
14	Correct	24 ms	23948 KB	Output is correct
15	Correct	27 ms	23848 KB	Output is correct
16	Correct	27 ms	23936 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	24056 KB	Output is correct
2	Correct	29 ms	23936 KB	Output is correct
3	Correct	25 ms	23928 KB	Output is correct
4	Correct	25 ms	23928 KB	Output is correct
5	Correct	26 ms	23936 KB	Output is correct
6	Correct	24 ms	23908 KB	Output is correct
7	Correct	26 ms	23952 KB	Output is correct
8	Correct	25 ms	23928 KB	Output is correct
9	Correct	27 ms	23960 KB	Output is correct
10	Correct	24 ms	23996 KB	Output is correct
11	Correct	25 ms	23928 KB	Output is correct
12	Correct	27 ms	23936 KB	Output is correct
13	Correct	25 ms	23928 KB	Output is correct
14	Correct	24 ms	23948 KB	Output is correct
15	Correct	27 ms	23848 KB	Output is correct
16	Correct	27 ms	23936 KB	Output is correct
17	Correct	28 ms	24316 KB	Output is correct
18	Correct	28 ms	24440 KB	Output is correct
19	Correct	31 ms	24320 KB	Output is correct
20	Correct	29 ms	24320 KB	Output is correct
21	Correct	31 ms	24312 KB	Output is correct
22	Correct	37 ms	24320 KB	Output is correct
23	Correct	35 ms	24312 KB	Output is correct

Subtask #4
39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	24056 KB	Output is correct
2	Correct	29 ms	23936 KB	Output is correct
3	Correct	25 ms	23928 KB	Output is correct
4	Correct	25 ms	23928 KB	Output is correct
5	Correct	26 ms	23936 KB	Output is correct
6	Correct	24 ms	23908 KB	Output is correct
7	Correct	26 ms	23952 KB	Output is correct
8	Correct	25 ms	23928 KB	Output is correct
9	Correct	27 ms	23960 KB	Output is correct
10	Correct	24 ms	23996 KB	Output is correct
11	Correct	25 ms	23928 KB	Output is correct
12	Correct	27 ms	23936 KB	Output is correct
13	Correct	25 ms	23928 KB	Output is correct
14	Correct	24 ms	23948 KB	Output is correct
15	Correct	27 ms	23848 KB	Output is correct
16	Correct	27 ms	23936 KB	Output is correct
17	Correct	28 ms	24316 KB	Output is correct
18	Correct	28 ms	24440 KB	Output is correct
19	Correct	31 ms	24320 KB	Output is correct
20	Correct	29 ms	24320 KB	Output is correct
21	Correct	31 ms	24312 KB	Output is correct
22	Correct	37 ms	24320 KB	Output is correct
23	Correct	35 ms	24312 KB	Output is correct
24	Correct	339 ms	66384 KB	Output is correct
25	Correct	373 ms	67836 KB	Output is correct
26	Correct	333 ms	66532 KB	Output is correct
27	Correct	379 ms	68016 KB	Output is correct
28	Correct	484 ms	68712 KB	Output is correct
29	Correct	442 ms	68700 KB	Output is correct
30	Correct	869 ms	70264 KB	Output is correct
31	Correct	281 ms	48588 KB	Output is correct
32	Correct	131 ms	43404 KB	Output is correct
33	Correct	537 ms	67544 KB	Output is correct
34	Correct	703 ms	69204 KB	Output is correct
35	Correct	822 ms	63980 KB	Output is correct
36	Correct	652 ms	63936 KB	Output is correct

Subtask #5
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	24056 KB	Output is correct
2	Correct	29 ms	23936 KB	Output is correct
3	Correct	25 ms	23928 KB	Output is correct
4	Correct	25 ms	23928 KB	Output is correct
5	Correct	26 ms	23936 KB	Output is correct
6	Correct	24 ms	23908 KB	Output is correct
7	Correct	26 ms	23952 KB	Output is correct
8	Correct	25 ms	23928 KB	Output is correct
9	Correct	27 ms	23960 KB	Output is correct
10	Correct	24 ms	23996 KB	Output is correct
11	Correct	25 ms	23928 KB	Output is correct
12	Correct	27 ms	23936 KB	Output is correct
13	Correct	25 ms	23928 KB	Output is correct
14	Correct	24 ms	23948 KB	Output is correct
15	Correct	27 ms	23848 KB	Output is correct
16	Correct	27 ms	23936 KB	Output is correct
17	Correct	28 ms	24316 KB	Output is correct
18	Correct	28 ms	24440 KB	Output is correct
19	Correct	31 ms	24320 KB	Output is correct
20	Correct	29 ms	24320 KB	Output is correct
21	Correct	31 ms	24312 KB	Output is correct
22	Correct	37 ms	24320 KB	Output is correct
23	Correct	35 ms	24312 KB	Output is correct
24	Correct	339 ms	66384 KB	Output is correct
25	Correct	373 ms	67836 KB	Output is correct
26	Correct	333 ms	66532 KB	Output is correct
27	Correct	379 ms	68016 KB	Output is correct
28	Correct	484 ms	68712 KB	Output is correct
29	Correct	442 ms	68700 KB	Output is correct
30	Correct	869 ms	70264 KB	Output is correct
31	Correct	281 ms	48588 KB	Output is correct
32	Correct	131 ms	43404 KB	Output is correct
33	Correct	537 ms	67544 KB	Output is correct
34	Correct	703 ms	69204 KB	Output is correct
35	Correct	822 ms	63980 KB	Output is correct
36	Correct	652 ms	63936 KB	Output is correct
37	Runtime error	56 ms	47644 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	24056 KB	Output is correct
2	Correct	29 ms	23936 KB	Output is correct
3	Correct	25 ms	23928 KB	Output is correct
4	Correct	25 ms	23928 KB	Output is correct
5	Correct	26 ms	23936 KB	Output is correct
6	Correct	24 ms	23908 KB	Output is correct
7	Correct	26 ms	23952 KB	Output is correct
8	Correct	25 ms	23928 KB	Output is correct
9	Correct	27 ms	23960 KB	Output is correct
10	Correct	24 ms	23996 KB	Output is correct
11	Correct	25 ms	23928 KB	Output is correct
12	Correct	27 ms	23936 KB	Output is correct
13	Correct	25 ms	23928 KB	Output is correct
14	Correct	24 ms	23948 KB	Output is correct
15	Correct	27 ms	23848 KB	Output is correct
16	Correct	27 ms	23936 KB	Output is correct
17	Correct	28 ms	24316 KB	Output is correct
18	Correct	28 ms	24440 KB	Output is correct
19	Correct	31 ms	24320 KB	Output is correct
20	Correct	29 ms	24320 KB	Output is correct
21	Correct	31 ms	24312 KB	Output is correct
22	Correct	37 ms	24320 KB	Output is correct
23	Correct	35 ms	24312 KB	Output is correct
24	Correct	339 ms	66384 KB	Output is correct
25	Correct	373 ms	67836 KB	Output is correct
26	Correct	333 ms	66532 KB	Output is correct
27	Correct	379 ms	68016 KB	Output is correct
28	Correct	484 ms	68712 KB	Output is correct
29	Correct	442 ms	68700 KB	Output is correct
30	Correct	869 ms	70264 KB	Output is correct
31	Correct	281 ms	48588 KB	Output is correct
32	Correct	131 ms	43404 KB	Output is correct
33	Correct	537 ms	67544 KB	Output is correct
34	Correct	703 ms	69204 KB	Output is correct
35	Correct	822 ms	63980 KB	Output is correct
36	Correct	652 ms	63936 KB	Output is correct
37	Runtime error	56 ms	47644 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Halted	0 ms	0 KB	-

Subtask #7
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	58 ms	47608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	58 ms	47608 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Submission #103853

Compilation message