Submission #72843235

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return (a > b) - (a < b);
}
int zac;
int zal[1024 * 4];
int zaq(int query) {
  int l = 0, r = zac - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (zal[m] == query) return m;
    else if (zal[m] < query) l = m + 1;
    else r = m - 1;
  }
  printf("ERROR: %d not found!\n", query);
  exit(72);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

int zac;
int zal[1024 * 4];

int zaq(int query) {
	int l = 0, r = zac - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (zal[m] == query) return m;
		else if (zal[m] < query) l = m + 1;
		else r = m - 1;
	}
	printf("ERROR: %d not found!\n", query);
	exit(72);
}

int w, h;
int n;
int x1[1024], y1[1024], x2[1024], y2[1024];

int wp, hp;

short maste[4096][4096];

struct yx_s {
	short y, x;
} q[4096 * 4096];

const int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

void nuru(int y, int x) {
	int i;
	int qs = 0, qe = 1;
	q[0] = (struct yx_s){ (short)y, (short)x };
	while (qs < qe) {
		struct yx_s cur = q[qs++];
		for (i = 0; i < 4; i++) {
			int ny = cur.y + d[i][0], nx = cur.x + d[i][1];
			if (0 <= ny && ny < hp && 0 <= nx  && nx < wp && maste[ny][nx] == 0) {
				maste[ny][nx] = -1;
				q[qe++] = (struct yx_s){ (short)ny, (short)nx };
			}
		}
	}
}

int main(void) {
	int i, j;
	int ans = 0;
	if (scanf("%d%d", &w, &h) != 2 ) return 1;
	if (scanf("%d", &n) != 1) return 1;
	for (i = 0; i < n; i++) {
		if (scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]) != 4) return 1;
		zal[i * 4 + 0] = x1[i];
		zal[i * 4 + 1] = y1[i];
		zal[i * 4 + 2] = x2[i];
		zal[i * 4 + 3] = y2[i];
	}
	zal[n * 4] = 0;
	zal[n * 4 + 1] = w;
	zal[n * 4 + 2] = h;
	qsort(zal, n * 4 + 3, sizeof(*zal), cmp);
	for (i = 1, zac = 1; i < n * 4 + 3; i++) {
		if (zal[zac - 1] != zal[i]) zal[zac++] = zal[i];
	}
	wp = zaq(w);
	hp = zaq(h);
	for (i = 0; i < n; i++) {
		int x1p = zaq(x1[i]), y1p = zaq(y1[i]), x2p = zaq(x2[i]), y2p = zaq(y2[i]);
		maste[y1p][x1p]++;
		maste[y1p][x2p]--;
		maste[y2p][x1p]--;
		maste[y2p][x2p]++;
	}
	for (i = 0; i < zac; i++) {
		for (j = 1; j < zac; j++) maste[i][j] += maste[i][j - 1];
	}
	for (j = 0; j < zac; j++) {
		for (i = 1; i < zac; i++) maste[i][j] += maste[i - 1][j];
	}
	for (i = 0; i < hp; i++) {
		for (j = 0; j < wp; j++) {
			if (maste[i][j] == 0) {
				nuru(i, j);
				ans++;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result