oj.uz

Submission #532364

# Submission time Handle Problem Language Result Execution time Memory
532364 2022-03-02T18:43:28 Z rainboy None (JOI14_ho_t5) C
30 / 100
 115 ms 8388 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 6 ms 332 KB Output is correct
14 Correct 4 ms 332 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 6 ms 332 KB Output is correct
14 Correct 4 ms 332 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 5 ms 356 KB Output is correct
22 Correct 3 ms 332 KB Output is correct
23 Correct 7 ms 332 KB Output is correct
24 Correct 5 ms 332 KB Output is correct
25 Correct 5 ms 332 KB Output is correct
26 Correct 3 ms 332 KB Output is correct
27 Correct 5 ms 332 KB Output is correct
28 Correct 7 ms 332 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 4 ms 296 KB Output is correct
5 Incorrect 11 ms 1100 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 6 ms 332 KB Output is correct
3 Correct 13 ms 1008 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 115 ms 8388 KB Output is correct
7 Correct 8 ms 944 KB Output is correct
8 Correct 76 ms 7368 KB Output is correct
9 Correct 86 ms 7484 KB Output is correct
10 Correct 80 ms 7240 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 5 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 6 ms 332 KB Output is correct
14 Correct 4 ms 332 KB Output is correct
15 Correct 4 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 5 ms 356 KB Output is correct
22 Correct 3 ms 332 KB Output is correct
23 Correct 7 ms 332 KB Output is correct
24 Correct 5 ms 332 KB Output is correct
25 Correct 5 ms 332 KB Output is correct
26 Correct 3 ms 332 KB Output is correct
27 Correct 5 ms 332 KB Output is correct
28 Correct 7 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 4 ms 296 KB Output is correct
33 Incorrect 11 ms 1100 KB Output isn't correct
34 Halted 0 ms 0 KB -