Submission #532364

#	Time	Username	Problem	Language	Result	Execution time	Memory
532364		rainboy	절취선 (JOI14_ho_t5)	C11	30 / 100	115 ms	8388 KiB

2014_ho_t5

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

#define N	100004

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

unsigned int X = 12345;

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

int xx[N * 2], yy[N * 2], tt[N * 2];

int (*compare)(int, int);

int compare_xt(int i, int j) {
	return xx[i] != xx[j] ? xx[i] - xx[j] : tt[j] - tt[i];
}

int compare_y(int i, int j) {
	return yy[i] - yy[j];
}

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

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

int intersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
	int tmp;

	if (x1 > x2)
		tmp = x1, x1 = x2, x2 = tmp;
	if (y1 > y2)
		tmp = y1, y1 = y2, y2 = tmp;
	if (x3 > x4)
		tmp = x3, x3 = x4, x4 = tmp;
	if (y3 > y4)
		tmp = y3, y3 = y4, y4 = tmp;
	return max(x1, x3) <= min(x2, x4) && max(y1, y3) <= min(y2, y4);
}

int ft[N * 2];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

long long get_ve(int n) {
	static int ii[N * 2];
	int n_, i;
	long long ve;

	n_ = 0;
	for (i = 0; i < n; i++) {
		ii[n_++] = i << 1 | 0;
		if (tt[i << 1 | 0] != 0)
			ii[n_++] = i << 1 | 1;
	}
	compare = compare_xt, sort(ii, 0, n_);
	ve = n;
	for (i = 0; i < n_; i++) {
		int i_ = ii[i];

		if (tt[i_] == 0)
			ve -= query(yy[i_ ^ 1]) - query(yy[i_] - 1);
		else
			update(yy[i_], n * 2, tt[i_]);
	}
	return ve;
}

int get_c(int n) {
	int i, j, c;

	if (n > 2000)
		return 1;
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (intersect(xx[i << 1 | 0], yy[i << 1 | 0], xx[i << 1 | 1], yy[i << 1 | 1], xx[j << 1 | 0], yy[j << 1 | 0], xx[j << 1 | 1], yy[j << 1 | 1]))
				join(i, j);
	c = 0;
	for (i = 0; i < n; i++)
		if (ds[i] < 0)
			c++;
	return c;
}

int main() {
	static int ii[N * 2];
	int w, h, n, i, y, tmp;

	scanf("%d%d%d", &w, &h, &n);
	for (i = 0; i < n * 2; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	xx[n << 1 | 0] = 0, yy[n << 1 | 0] = 0, xx[n << 1 | 1] = w, yy[n << 1 | 1] = 0;
	xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
	xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
	xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
	n += 4;
	for (i = 0; i < n; i++) {
		if (xx[i << 1 | 0] > xx[i << 1 | 1])
			tmp = xx[i << 1 | 0], xx[i << 1 | 0] = xx[i << 1 | 1], xx[i << 1 | 1] = tmp;
		if (yy[i << 1 | 0] > yy[i << 1 | 1])
			tmp = yy[i << 1 | 0], yy[i << 1 | 0] = yy[i << 1 | 1], yy[i << 1 | 1] = tmp;
	}
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	for (i = 0; i < n * 2; i++)
		tt[i] = xx[i] == xx[i ^ 1] ? 0 : ((i & 1) == 0 ? 1 : -1);
	compare = compare_y, sort(ii, 0, n * 2);
	for (i = 0, y = 0; i < n * 2; i++)
		yy[ii[i]] = i + 1 == n * 2 || yy[ii[i + 1]] != yy[ii[i]] ? y++ : y;
	printf("%lld\n", get_c(n) - get_ve(n));
	return 0;
}

Compilation message (stderr)

2014_ho_t5.c: In function 'main':
2014_ho_t5.c:151:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  151 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |     ~~^~~
2014_ho_t5.c:151:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  151 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |                             ~~^~~
2014_ho_t5.c:151:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  151 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |                                                     ~~^~~
2014_ho_t5.c:151:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  151 |  xx[n + 1 << 1 | 0] = w, yy[n + 1 << 1 | 0] = 0, xx[n + 1 << 1 | 1] = w, yy[n + 1 << 1 | 1] = h;
      |                                                                             ~~^~~
2014_ho_t5.c:152:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  152 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |     ~~^~~
2014_ho_t5.c:152:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  152 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |                             ~~^~~
2014_ho_t5.c:152:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  152 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |                                                     ~~^~~
2014_ho_t5.c:152:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  152 |  xx[n + 2 << 1 | 0] = w, yy[n + 2 << 1 | 0] = h, xx[n + 2 << 1 | 1] = 0, yy[n + 2 << 1 | 1] = h;
      |                                                                             ~~^~~
2014_ho_t5.c:153:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  153 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |     ~~^~~
2014_ho_t5.c:153:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  153 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |                             ~~^~~
2014_ho_t5.c:153:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  153 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |                                                     ~~^~~
2014_ho_t5.c:153:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  153 |  xx[n + 3 << 1 | 0] = 0, yy[n + 3 << 1 | 0] = h, xx[n + 3 << 1 | 1] = 0, yy[n + 3 << 1 | 1] = 0;
      |                                                                             ~~^~~
2014_ho_t5.c:147:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |  scanf("%d%d%d", &w, &h, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.c:149:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 50