oj.uz

Submission #673687

# Submission time Handle Problem Language Result Execution time Memory
673687 2022-12-21T17:00:32 Z rainboy Two Dishes (JOI19_dishes) C
91 / 100
 5792 ms 226220 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	1000000
#define M	1000000
#define N_	(1 << 20)	/* N_ = pow2(ceil(log2(M + 1))) */
#define INF	0x3f3f3f3f3f3f3f3fLL

long long max(long long a, long long b) { return a > b ? a : b; }

int *ej[N], *ev[N], eo[N];

void append(int i, int j, int v) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0) {
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
		ev[i] = (int *) realloc(ev[i], o * 2 * sizeof *ev[i]);
	}
	ej[i][o] = j, ev[i][o] = v;
}

long long st[N_ * 2], lz1[N_], lz2[N_]; int h_, n_;

void build(int n) {
	int i;

	h_ = 0;
	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	for (i = 1; i < n_ * 2; i++)
		st[i] = -INF, lz1[i] = -INF, lz2[i] = 0;
}

void put(int i, long long x, long long y) {
	st[i] = max(st[i], x);
	if (st[i] != -INF)
		st[i] += y;
	if (i < n_)
		lz1[i] = max(lz1[i], x - lz2[i]), lz2[i] += y;
}

void pus(int i) {
	if (lz1[i] != -INF || lz2[i] != 0)
		put(i << 1 | 0, lz1[i], lz2[i]), put(i << 1 | 1, lz1[i], lz2[i]), lz1[i] = -INF, lz2[i] = 0;
}

void pul(int i) {
	if (lz1[i] == -INF && lz2[i] == 0)
		st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void update(int l, int r, long long x, long long y) {
	int l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, x, y);
		if ((r & 1) == 0)
			put(r--, x, y);
	}
	pull(l_), pull(r_);
}

long long query(int i) {
	push(i += n_);
	return st[i];
}

int main() {
	static long long aa[N], ss[N], bb[M], tt[M];
	static int pp[N], qq[M];
	int n, m, i, j, v, o, lower, upper;
	long long x;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%lld%lld%d", &aa[i], &ss[i], &pp[i]);
	for (i = 1; i < n; i++)
		aa[i] += aa[i - 1];
	for (j = 0; j < m; j++)
		scanf("%lld%lld%d", &bb[j], &tt[j], &qq[j]);
	for (j = 1; j < m; j++)
		bb[j] += bb[j - 1];
	for (i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		ev[i] = (int *) malloc(2 * sizeof *ev[i]);
	}
	x = 0;
	for (i = 0; i < n; i++) {
		if (aa[i] > ss[i])
			continue;
		if (aa[i] + bb[m - 1] <= ss[i]) {
			x += pp[i];
			continue;
		}
		lower = -1, upper = m - 1;
		while (upper - lower > 1) {
			j = (lower + upper) / 2;
			if (aa[i] + bb[j] <= ss[i])
				lower = j;
			else
				upper = j;
		}
		j = upper;
		append(i, j, pp[i]);
	}
	for (j = 0; j < m; j++) {
		if (bb[j] > tt[j])
			continue;
		x += qq[j];
		if (aa[n - 1] + bb[j] <= tt[j])
			continue;
		lower = -1, upper = n - 1;
		while (upper - lower > 1) {
			i = (lower + upper) / 2;
			if (aa[i] + bb[j] <= tt[j])
				lower = i;
			else
				upper = i;
		}
		i = upper;
		append(i, j, -qq[j]);
	}
	build(m + 1);
	update(0, m, x, 0);
	for (i = 0; i < n; i++) {
		for (o = eo[i]; o--; ) {
			j = ej[i][o], v = ev[i][o];
			update(0, j, -INF, v);
		}
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			update(j + 1, m, query(j), 0);
		}
	}
	printf("%lld\n", query(m));
	return 0;
}

Compilation message

dishes.c: In function 'append':
dishes.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
dishes.c: In function 'main':
dishes.c:90:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
dishes.c:92:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%lld%lld%d", &aa[i], &ss[i], &pp[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.c:96:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%lld%lld%d", &bb[j], &tt[j], &qq[j]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 50664 KB Output is correct
2 Correct 583 ms 50188 KB Output is correct
3 Correct 225 ms 49504 KB Output is correct
4 Correct 456 ms 49724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 543 ms 49528 KB Output is correct
7 Correct 84 ms 23328 KB Output is correct
8 Correct 91 ms 26920 KB Output is correct
9 Correct 232 ms 50500 KB Output is correct
10 Correct 605 ms 44340 KB Output is correct
11 Correct 146 ms 43944 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 300 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 3 ms 820 KB Output is correct
18 Correct 3 ms 820 KB Output is correct
19 Correct 5 ms 724 KB Output is correct
20 Correct 4 ms 692 KB Output is correct
21 Correct 4 ms 724 KB Output is correct
22 Correct 5 ms 696 KB Output is correct
23 Correct 6 ms 768 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 300 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 3 ms 820 KB Output is correct
18 Correct 3 ms 820 KB Output is correct
19 Correct 5 ms 724 KB Output is correct
20 Correct 4 ms 692 KB Output is correct
21 Correct 4 ms 724 KB Output is correct
22 Correct 5 ms 696 KB Output is correct
23 Correct 6 ms 768 KB Output is correct
24 Correct 476 ms 47504 KB Output is correct
25 Correct 485 ms 48444 KB Output is correct
26 Correct 444 ms 47624 KB Output is correct
27 Correct 409 ms 47684 KB Output is correct
28 Correct 433 ms 47660 KB Output is correct
29 Correct 160 ms 47388 KB Output is correct
30 Correct 867 ms 47824 KB Output is correct
31 Correct 190 ms 22880 KB Output is correct
32 Correct 91 ms 25836 KB Output is correct
33 Correct 546 ms 46904 KB Output is correct
34 Correct 663 ms 47596 KB Output is correct
35 Correct 843 ms 41276 KB Output is correct
36 Correct 777 ms 41388 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 300 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 3 ms 820 KB Output is correct
18 Correct 3 ms 820 KB Output is correct
19 Correct 5 ms 724 KB Output is correct
20 Correct 4 ms 692 KB Output is correct
21 Correct 4 ms 724 KB Output is correct
22 Correct 5 ms 696 KB Output is correct
23 Correct 6 ms 768 KB Output is correct
24 Correct 476 ms 47504 KB Output is correct
25 Correct 485 ms 48444 KB Output is correct
26 Correct 444 ms 47624 KB Output is correct
27 Correct 409 ms 47684 KB Output is correct
28 Correct 433 ms 47660 KB Output is correct
29 Correct 160 ms 47388 KB Output is correct
30 Correct 867 ms 47824 KB Output is correct
31 Correct 190 ms 22880 KB Output is correct
32 Correct 91 ms 25836 KB Output is correct
33 Correct 546 ms 46904 KB Output is correct
34 Correct 663 ms 47596 KB Output is correct
35 Correct 843 ms 41276 KB Output is correct
36 Correct 777 ms 41388 KB Output is correct
37 Correct 424 ms 50624 KB Output is correct
38 Correct 435 ms 50644 KB Output is correct
39 Correct 678 ms 47964 KB Output is correct
40 Correct 656 ms 47976 KB Output is correct
41 Correct 0 ms 340 KB Output is correct
42 Correct 886 ms 50912 KB Output is correct
43 Correct 507 ms 49724 KB Output is correct
44 Correct 777 ms 50600 KB Output is correct
45 Correct 811 ms 44520 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 0 ms 296 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 300 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 3 ms 820 KB Output is correct
18 Correct 3 ms 820 KB Output is correct
19 Correct 5 ms 724 KB Output is correct
20 Correct 4 ms 692 KB Output is correct
21 Correct 4 ms 724 KB Output is correct
22 Correct 5 ms 696 KB Output is correct
23 Correct 6 ms 768 KB Output is correct
24 Correct 476 ms 47504 KB Output is correct
25 Correct 485 ms 48444 KB Output is correct
26 Correct 444 ms 47624 KB Output is correct
27 Correct 409 ms 47684 KB Output is correct
28 Correct 433 ms 47660 KB Output is correct
29 Correct 160 ms 47388 KB Output is correct
30 Correct 867 ms 47824 KB Output is correct
31 Correct 190 ms 22880 KB Output is correct
32 Correct 91 ms 25836 KB Output is correct
33 Correct 546 ms 46904 KB Output is correct
34 Correct 663 ms 47596 KB Output is correct
35 Correct 843 ms 41276 KB Output is correct
36 Correct 777 ms 41388 KB Output is correct
37 Correct 424 ms 50624 KB Output is correct
38 Correct 435 ms 50644 KB Output is correct
39 Correct 678 ms 47964 KB Output is correct
40 Correct 656 ms 47976 KB Output is correct
41 Correct 0 ms 340 KB Output is correct
42 Correct 886 ms 50912 KB Output is correct
43 Correct 507 ms 49724 KB Output is correct
44 Correct 777 ms 50600 KB Output is correct
45 Correct 811 ms 44520 KB Output is correct
46 Correct 2307 ms 224372 KB Output is correct
47 Correct 2308 ms 224348 KB Output is correct
48 Correct 3609 ms 210752 KB Output is correct
49 Correct 3426 ms 210776 KB Output is correct
50 Correct 5792 ms 225284 KB Output is correct
51 Correct 3017 ms 214912 KB Output is correct
52 Correct 3978 ms 219368 KB Output is correct
53 Correct 5247 ms 193984 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 50664 KB Output is correct
2 Correct 583 ms 50188 KB Output is correct
3 Correct 225 ms 49504 KB Output is correct
4 Correct 456 ms 49724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 543 ms 49528 KB Output is correct
7 Correct 84 ms 23328 KB Output is correct
8 Correct 91 ms 26920 KB Output is correct
9 Correct 232 ms 50500 KB Output is correct
10 Correct 605 ms 44340 KB Output is correct
11 Correct 146 ms 43944 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 0 ms 296 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 296 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 300 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 3 ms 820 KB Output is correct
29 Correct 3 ms 820 KB Output is correct
30 Correct 5 ms 724 KB Output is correct
31 Correct 4 ms 692 KB Output is correct
32 Correct 4 ms 724 KB Output is correct
33 Correct 5 ms 696 KB Output is correct
34 Correct 6 ms 768 KB Output is correct
35 Correct 476 ms 47504 KB Output is correct
36 Correct 485 ms 48444 KB Output is correct
37 Correct 444 ms 47624 KB Output is correct
38 Correct 409 ms 47684 KB Output is correct
39 Correct 433 ms 47660 KB Output is correct
40 Correct 160 ms 47388 KB Output is correct
41 Correct 867 ms 47824 KB Output is correct
42 Correct 190 ms 22880 KB Output is correct
43 Correct 91 ms 25836 KB Output is correct
44 Correct 546 ms 46904 KB Output is correct
45 Correct 663 ms 47596 KB Output is correct
46 Correct 843 ms 41276 KB Output is correct
47 Correct 777 ms 41388 KB Output is correct
48 Correct 424 ms 50624 KB Output is correct
49 Correct 435 ms 50644 KB Output is correct
50 Correct 678 ms 47964 KB Output is correct
51 Correct 656 ms 47976 KB Output is correct
52 Correct 0 ms 340 KB Output is correct
53 Correct 886 ms 50912 KB Output is correct
54 Correct 507 ms 49724 KB Output is correct
55 Correct 777 ms 50600 KB Output is correct
56 Correct 811 ms 44520 KB Output is correct
57 Correct 412 ms 51004 KB Output is correct
58 Correct 416 ms 51156 KB Output is correct
59 Correct 669 ms 48964 KB Output is correct
60 Correct 650 ms 48980 KB Output is correct
61 Correct 734 ms 47904 KB Output is correct
62 Correct 0 ms 296 KB Output is correct
63 Correct 896 ms 51032 KB Output is correct
64 Correct 515 ms 50300 KB Output is correct
65 Correct 679 ms 49908 KB Output is correct
66 Correct 786 ms 44812 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 50664 KB Output is correct
2 Correct 583 ms 50188 KB Output is correct
3 Correct 225 ms 49504 KB Output is correct
4 Correct 456 ms 49724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 543 ms 49528 KB Output is correct
7 Correct 84 ms 23328 KB Output is correct
8 Correct 91 ms 26920 KB Output is correct
9 Correct 232 ms 50500 KB Output is correct
10 Correct 605 ms 44340 KB Output is correct
11 Correct 146 ms 43944 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 0 ms 296 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 296 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 300 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 3 ms 820 KB Output is correct
29 Correct 3 ms 820 KB Output is correct
30 Correct 5 ms 724 KB Output is correct
31 Correct 4 ms 692 KB Output is correct
32 Correct 4 ms 724 KB Output is correct
33 Correct 5 ms 696 KB Output is correct
34 Correct 6 ms 768 KB Output is correct
35 Correct 476 ms 47504 KB Output is correct
36 Correct 485 ms 48444 KB Output is correct
37 Correct 444 ms 47624 KB Output is correct
38 Correct 409 ms 47684 KB Output is correct
39 Correct 433 ms 47660 KB Output is correct
40 Correct 160 ms 47388 KB Output is correct
41 Correct 867 ms 47824 KB Output is correct
42 Correct 190 ms 22880 KB Output is correct
43 Correct 91 ms 25836 KB Output is correct
44 Correct 546 ms 46904 KB Output is correct
45 Correct 663 ms 47596 KB Output is correct
46 Correct 843 ms 41276 KB Output is correct
47 Correct 777 ms 41388 KB Output is correct
48 Correct 424 ms 50624 KB Output is correct
49 Correct 435 ms 50644 KB Output is correct
50 Correct 678 ms 47964 KB Output is correct
51 Correct 656 ms 47976 KB Output is correct
52 Correct 0 ms 340 KB Output is correct
53 Correct 886 ms 50912 KB Output is correct
54 Correct 507 ms 49724 KB Output is correct
55 Correct 777 ms 50600 KB Output is correct
56 Correct 811 ms 44520 KB Output is correct
57 Correct 2307 ms 224372 KB Output is correct
58 Correct 2308 ms 224348 KB Output is correct
59 Correct 3609 ms 210752 KB Output is correct
60 Correct 3426 ms 210776 KB Output is correct
61 Correct 5792 ms 225284 KB Output is correct
62 Correct 3017 ms 214912 KB Output is correct
63 Correct 3978 ms 219368 KB Output is correct
64 Correct 5247 ms 193984 KB Output is correct
65 Correct 412 ms 51004 KB Output is correct
66 Correct 416 ms 51156 KB Output is correct
67 Correct 669 ms 48964 KB Output is correct
68 Correct 650 ms 48980 KB Output is correct
69 Correct 734 ms 47904 KB Output is correct
70 Correct 0 ms 296 KB Output is correct
71 Correct 896 ms 51032 KB Output is correct
72 Correct 515 ms 50300 KB Output is correct
73 Correct 679 ms 49908 KB Output is correct
74 Correct 786 ms 44812 KB Output is correct
75 Incorrect 2317 ms 226220 KB Output isn't correct
76 Halted 0 ms 0 KB -