Submission #705312

#	Time	Username	Problem	Language	Result	Execution time	Memory
705312		rainboy	Rope (JOI17_rope)	C11	100 / 100	1118 ms	72776 KiB

rope

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

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

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int *ei[M], eo[M];

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

	if (o >= 2 && (o & o - 1) == 0)
		ei[a] = (int *) realloc(ei[a], o * 2 * sizeof *ei[a]);
	ei[a][o] = i;
}

int st[N_ * 2], n_;

void pul(int i) {
	st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}

void update(int i, int x) {
	st[i += n_] += x;
	while (i > 1)
		pul(i >>= 1);
}

int main() {
	static int aa[N], ans[M];
	int n, m, r, i, a, o, ka, kb;

	scanf("%d%d", &n, &m);
	if (m == 1) {
		printf("0\n");
		return 0;
	}
	for (a = 0; a < n; a++)
		ei[a] = (int *) malloc(2 * sizeof *ei[a]);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]), aa[i]--;
		append(aa[i], i);
	}
	n_ = 1;
	while (n_ < m)
		n_ <<= 1;
	for (i = 0; i < n; i++)
		update(aa[i], 1);
	memset(ans, 0x3f, n * sizeof *ans);
	for (r = 0; r < 2; r++)
		for (a = 0; a < m; a++) {
			ka = st[n_ + a];
			for (o = eo[a]; o--; ) {
				i = ei[a][o];
				update(aa[i], -1);
				if (i % 2 == r) {
					if (i > 0)
						update(aa[i - 1], -1);
				} else {
					if (i + 1 < n)
						update(aa[i + 1], -1);
				}
			}
			kb = st[1];
			ans[a] = min(ans[a], n - ka - kb);
			for (o = eo[a]; o--; ) {
				i = ei[a][o];
				update(aa[i], 1);
				if (i % 2 == r) {
					if (i > 0)
						update(aa[i - 1], 1);
				} else {
					if (i + 1 < n)
						update(aa[i + 1], 1);
				}
			}
		}
	for (a = 0; a < m; a++)
		printf("%d\n", ans[a]);
	return 0;
}

Compilation message (stderr)

rope.c: In function 'append':
rope.c:17:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   17 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
rope.c: In function 'main':
rope.c:38:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
rope.c:46:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20