Submission #788181

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
788181	2023-07-19T21:34:57 Z	rainboy	Fruits (NOI22_fruits)	C	35 / 100	1000 ms	15336 KB

Main

#include <stdio.h>
#include <string.h>

#define N	400000

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

long long ss[N + 1];
int xx[N], yy[N], dd[N]; long long dp[N]; int pp[N], qq[N], hh[N], tt[N];
int n, m;

int cross(int i, int j) {
	int lower = -1, upper = m - yy[j] + 1;

	while (upper - lower > 1) {
		int d = (lower + upper) / 2;

		if (dp[i] - ss[yy[i] + d] > dp[j] - ss[yy[j] + d])
			upper = d;
		else
			lower = d;
	}
	return lower;
}

void merge(int i, int j) {
	int u, v, d;

	u = tt[i], v = hh[j];
	while (1) {
		d = cross(u, v);
		if (u != hh[i] && cross(pp[u], u) <= d)
			u = pp[u];
		else if (v != tt[j] && cross(v, qq[v]) >= d)
			v = qq[v];
		else {
			qq[u] = v, pp[v] = u;
			break;
		}
	}
	hh[j] = hh[i];
}

long long query(int i, int d) {
	while (hh[i] != tt[i] && cross(hh[i], qq[hh[i]]) >= d)
		hh[i] = qq[hh[i]];
	return dp[hh[i]] - ss[yy[hh[i]] + d];
}

int main() {
	static int aa[N], ii[N], ww[N], qu[N];
	int cnt, i, i_, j, a, x, y, d;
	long long z;

	scanf("%d", &n);
	memset(ii, -1, n * sizeof *ii);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]), aa[i]--;
		if (aa[i] >= 0)
			ii[aa[i]] = i;
	}
	for (a = 0; a < n; a++)
		scanf("%d", &ww[a]);
	m = 0;
	for (a = 0; a < n; a++)
		if ((i = ii[a]) != -1)
			xx[i] = m;
		else
			ss[m + 1] = ss[m] + ww[a], m++;
	if (m == n) {
		for (i = 0; i < n; i++)
			printf("%lld ", ss[n] - ss[n - 1 - i]);
		printf("\n");
		return 0;
	}
	for (i = 0; i < n; i++)
		pp[i] = qq[i] = -1, hh[i] = tt[i] = i;
	cnt = 0, y = 0, a = -1;
	for (j = 0; j < n; j++) {
		if (aa[j] == -2)
			y++;
		else if (a > aa[j])
			aa[j] = -1;
		else {
			a = aa[j];
			yy[j] = y, dd[j] = xx[j] - yy[j];
			if (dd[j] < 0)
				aa[j] = -1;
		}
		if (aa[j] >= 0) {
			i_ = -1;
			while (cnt && dd[i = qu[cnt - 1]] < dd[j]) {
				if (i_ == -1)
					i_ = i;
				else
					merge(i, i_);
				cnt--;
			}
			dp[j] = cnt ? dp[i] - ss[xx[i]] : -ss[dd[j]];
			if (i_ != -1)
				dp[j] = max(dp[j], query(i_, dd[j]));
			dp[j] += ss[xx[j]] + ww[aa[j]];
			if (i_ != -1)
				merge(i_, j);
			qu[cnt++] = j;
		}
		x = m, d = x - y;
		z = 0;
		for (i = j; i >= 0; i--) {
			if (aa[i] < 0)
				continue;
			if (dd[i] >= d)
				break;
			z = max(z, dp[i] + ss[x] - ss[yy[i] + d]);
		}
		if (i >= 0)
			z = max(z, dp[i] + ss[x] - ss[xx[i]]);
		else
			z = max(z, ss[x] - ss[d]);
		printf("%lld ", z);
	}
	printf("\n");
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:55:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:58:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:63:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%d", &ww[a]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct
6	Correct	340 KB	Output is correct
7	Correct	340 KB	Output is correct
8	Correct	340 KB	Output is correct
9	Correct	340 KB	Output is correct
10	Correct	340 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	5 ms	852 KB	Output is correct
4	Correct	46 ms	6856 KB	Output is correct
5	Correct	87 ms	13536 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 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	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	352 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	0 ms	340 KB	Output is correct

Subtask #4
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	1 ms	340 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	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	352 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	0 ms	340 KB	Output is correct
28	Correct	1 ms	476 KB	Output is correct
29	Correct	4 ms	468 KB	Output is correct
30	Correct	2 ms	468 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	2 ms	468 KB	Output is correct
34	Correct	2 ms	476 KB	Output is correct
35	Correct	1 ms	596 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	1 ms	316 KB	Output is correct
38	Correct	2 ms	468 KB	Output is correct
39	Correct	2 ms	428 KB	Output is correct
40	Correct	2 ms	468 KB	Output is correct
41	Correct	2 ms	468 KB	Output is correct
42	Correct	3 ms	432 KB	Output is correct
43	Correct	2 ms	468 KB	Output is correct
44	Correct	3 ms	468 KB	Output is correct
45	Correct	4 ms	468 KB	Output is correct
46	Correct	3 ms	436 KB	Output is correct
47	Correct	0 ms	292 KB	Output is correct
48	Correct	1 ms	340 KB	Output is correct

Subtask #5
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1074 ms	15336 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	5 ms	852 KB	Output is correct
14	Correct	46 ms	6856 KB	Output is correct
15	Correct	87 ms	13536 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	0 ms	340 KB	Output is correct
28	Correct	0 ms	352 KB	Output is correct
29	Correct	0 ms	340 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	0 ms	340 KB	Output is correct
33	Correct	0 ms	340 KB	Output is correct
34	Correct	1 ms	476 KB	Output is correct
35	Correct	4 ms	468 KB	Output is correct
36	Correct	2 ms	468 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	1 ms	340 KB	Output is correct
39	Correct	2 ms	468 KB	Output is correct
40	Correct	2 ms	476 KB	Output is correct
41	Correct	1 ms	596 KB	Output is correct
42	Correct	1 ms	340 KB	Output is correct
43	Correct	1 ms	316 KB	Output is correct
44	Correct	2 ms	468 KB	Output is correct
45	Correct	2 ms	428 KB	Output is correct
46	Correct	2 ms	468 KB	Output is correct
47	Correct	2 ms	468 KB	Output is correct
48	Correct	3 ms	432 KB	Output is correct
49	Correct	2 ms	468 KB	Output is correct
50	Correct	3 ms	468 KB	Output is correct
51	Correct	4 ms	468 KB	Output is correct
52	Correct	3 ms	436 KB	Output is correct
53	Correct	0 ms	292 KB	Output is correct
54	Correct	1 ms	340 KB	Output is correct
55	Execution timed out	1074 ms	15336 KB	Time limit exceeded
56	Halted	0 ms	0 KB	-

Submission #788181

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 5.0 / 5.0

Subtask #3 11.0 / 11.0

Subtask #4 13.0 / 13.0

Subtask #5 0 / 23.0

Subtask #6 0 / 42.0

Subtask #1
6.0 / 6.0

Subtask #2
5.0 / 5.0

Subtask #3
11.0 / 11.0

Subtask #4
13.0 / 13.0

Subtask #5
0 / 23.0

Subtask #6
0 / 42.0