Submission #532367

#	Time	Username	Problem	Language	Result	Execution time	Memory
532367		rainboy	절취선 (JOI14_ho_t5)	C11	100 / 100	193 ms	10456 KiB

2014_ho_t5

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

#define N	100004
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N * 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 X = 12345;

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

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

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 ft[N * 2];

void ft_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) {
	int h;
	long long ve;

	ve = n;
	for (h = 0; h < m; h++) {
		int i = ii[h];

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

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 st[N_ * 2], n_;

void pul(int i) {
	int l = i << 1 | 0, r = l | 1;

	if (st[l] == -2 || st[r] == -2)
		st[i] = -2;
	else if (st[l] == -1)
		st[i] = st[r];
	else if (st[r] == -1)
		st[i] = st[l];
	else
		st[i] = find(st[l]) != find(st[r]) ? -2 : st[l];
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void st_update(int i, int u) {
	i += n_, st[i] = u, pull(i);
}

void join1(int i, int u) {
	if (st[i] == -1)
		return;
	if (st[i] != -2) {
		join(u, st[i]);
		return;
	}
	join1(i << 1 | 0, u), join1(i << 1 | 1, u);
	pul(i);
}

void join_(int l, int r, int u) {
	int l_ = l += n_, r_ = r += n_;

	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			join1(l++, u);
		if ((r & 1) == 0)
			join1(r--, u);
	}
	pull(l_), pull(r_);
}

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

	n_ = 1;
	while (n_ < n * 2)
		n_ <<= 1;
	memset(st, -1, n_ * 2 * sizeof *st);
	memset(ds, -1, n * sizeof *ds);
	for (h = 0; h < m; h++) {
		i = ii[h];
		if (tt[i] == 0)
			join_(yy[i], yy[i ^ 1], i >> 1);
		else
			st_update(yy[i], tt[i] == 1 ? i >> 1 : -1);
	}
	c = 0;
	for (i = 0; i < n; i++)
		if (ds[i] < 0)
			c++;
	return c;
}

int main() {
	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;
	m = 0;
	for (i = 0; i < n; i++) {
		ii[m++] = i << 1 | 0;
		if (tt[i << 1 | 0] != 0)
			ii[m++] = i << 1 | 1;
	}
	compare = compare_xt, sort(ii, 0, m);
	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:181:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  181 |  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:181:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  181 |  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:181:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  181 |  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:181:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  181 |  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:182:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  182 |  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:182:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  182 |  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:182:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  182 |  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:182:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  182 |  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:183:7: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  183 |  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:183:31: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  183 |  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:183:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  183 |  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:183:79: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  183 |  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:177:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |  scanf("%d%d%d", &w, &h, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.c:179:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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