Submission #1014836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014836		rainboy	Fire (BOI24_fire)	C11	100 / 100	142 ms	62800 KiB

Main

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

#define M	200000
#define N	(M * 2)

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

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int xx[M * 2], ij[M * 2], m;

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (xx[hh[j]] == xx[h])
				j++;
			else if (xx[hh[j]] < xx[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

int *ej[N * 2], eo[N * 2], n;

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

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

int qu[N * 2], ans;

void dfs(int i, int d) {
	int o;

	qu[d] = i;
	if (i < n) {
		ans = min(ans, d + 1);
		while (ans > 0 && qu[d - (ans - 1)] - i >= n)
			ans--;
	}
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(j, d + 1);
	}
}

int main() {
	static int hh[M * 2], jj[N];
	int h, i, j;

	scanf("%d%*d", &m);
	for (h = 0; h < m * 2; h++)
		scanf("%d", &xx[h]);
	for (h = 0; h < m * 2; h++)
		hh[h] = h;
	sort(hh, 0, m * 2);
	n = 0;
	for (h = 0; h < m * 2; h++)
		ij[hh[h]] = h + 1 == m * 2 || xx[hh[h + 1]] != xx[hh[h]] ? n++ : n;
	for (i = 0; i < n; i++)
		jj[i] = i;
	for (h = 0; h < m; h++) {
		i = ij[h << 1 | 0], j = ij[h << 1 | 1];
		if (i < j)
			jj[i] = max(jj[i], j);
		else
			jj[0] = max(jj[0], j), jj[i] = max(jj[i], n + j);
	}
	for (i = 1; i < n; i++)
		jj[i] = max(jj[i], jj[i - 1]);
	for (i = 0; i < n; i++)
		if (jj[i] == i) {
			printf("-1\n");
			return 0;
		}
	for (i = 0; i < n * 2; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (i = 0; i < n; i++) {
		append(jj[i], i);
		if (jj[i] < n)
			append(n + jj[i], n + i);
	}
	ans = m;
	for (i = 0; i < n; i++)
		if (jj[i] >= n)
			dfs(n + i, 0);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:42:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   42 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:69:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d%*d", &m);
      |  ^~~~~~~~~~~~~~~~~~
Main.c:71:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d", &xx[h]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26