oj.uz

Submission #685204

# Submission time Handle Problem Language Result Execution time Memory
685204 2023-01-23T17:02:59 Z rainboy Dragon 2 (JOI17_dragon2) C
100 / 100
 2717 ms 60296 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	30000
#define N8	(N * 8)
#define LN	16	/* LN = ceil(log2(N * 2 + 1)) */
#define N_	(N8 * (LN + 1) + 1)

unsigned int X = 12345;

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

int *ei[N], *ei1[N], *ei2[N], *et1[N], *et2[N], eo[N], n, n_;
int xx[N + 2], yy[N + 2], cc[N], xx_[N], yy_[N], xx1[N8], yy1[N8];

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

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

long long cross2(int x1, int y1, int x2, int y2) {
	return (long long) x1 * y2 - (long long) x2 * y1;
}

long long cross(int i, int j, int k) {
	return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}

int u;

int compare_c(int i, int j) {
	int si = xx[i] < xx[u] || xx[i] == xx[u] && yy[i] < yy[u] ? -1 : 1;
	int sj = xx[j] < xx[u] || xx[j] == xx[u] && yy[j] < yy[u] ? -1 : 1;
	long long c;

	if (si != sj)
		return si - sj;
	c = cross(u, i, j);
	return c == 0 ? 0 : (c < 0 ? -1 : 1);
}

int compare_x1(int i, int j) {
	return xx1[i] - xx1[j];
}

int (*compare)(int, int);

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 ll[N_], rr[N_], sum[N_];

int update(int t, int l, int r, int i, int x) {
	static int _ = 1;
	int t_ = _++;

	sum[t_] = sum[t] + x, ll[t_] = ll[t], rr[t_] = rr[t];
	if (r - l > 1) {
		int m = (l + r) / 2;

		if (i < m)
			ll[t_] = update(ll[t_], l, m, i, x);
		else
			rr[t_] = update(rr[t_], m, r, i, x);
	}
	return t_;
}

int query(int t, int l, int r, int ql, int qr) {
	int m;

	if (qr <= l || r <= ql)
		return 0;
	if (ql <= l && r <= qr)
		return sum[t];
	m = (l + r) / 2;
	return query(ll[t], l, m, ql, qr) + query(rr[t], m, r, ql, qr);
}

void add(int **ei, int a, int o, int i, int x, int y) {
	xx1[i] = x, yy1[i] = y, ei[a][o] = i;
}

int query_(int *ii, int *tt, int m, int x, int yl, int yr) {
	int lower = -1, upper = m;

	while (upper - lower > 1) {
		int h = (lower + upper) / 2;

		if (xx1[ii[h]] < x)
			lower = h;
		else
			upper = h;
	}
	return lower == -1 ? 0 : query(tt[lower], 0, n_, yl, yr);
}

int main() {
	static int ii[N], jj0[N], jj1[N];
	int m, q, i, j, a, b, c, o, ans;

	scanf("%d%d", &n, &m), n_ = n * 2 + 1;
	for (c = 0; c < m; c++) {
		ei[c] = (int *) malloc(2 * sizeof *ei[c]);
		ei1[c] = (int *) malloc(2 * sizeof *ei1[c]);
		ei2[c] = (int *) malloc(2 * sizeof *ei2[c]);
	}
	for (i = 0; i < n; i++) {
		scanf("%d%d%d", &xx[i], &yy[i], &cc[i]), cc[i]--;
		append(cc[i], i);
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	scanf("%d%d%d%d", &xx[n], &yy[n], &xx[n + 1], &yy[n + 1]);
	compare = compare_c, u = n, sort(ii, 0, n);
	for (i = 0; i < n; i++)
		xx_[ii[i]] = i;
	for (i = 0, j = 0; i < n; i++) {
		while (j < i + n && cross(u, ii[i], ii[j % n]) <= 0)
			j++;
		jj0[i] = j;
	}
	compare = compare_c, u = n + 1, sort(ii, 0, n);
	for (i = 0; i < n; i++)
		yy_[ii[i]] = i;
	for (i = 0, j = 0; i < n; i++) {
		while (j < i + n && cross(u, ii[i], ii[j % n]) <= 0)
			j++;
		jj1[i] = j;
	}
	for (a = 0; a < m; a++) {
		ei1[a] = (int *) malloc(eo[a] * 4 * sizeof *ei1[a]);
		ei2[a] = (int *) malloc(eo[a] * 4 * sizeof *ei2[a]);
		for (o = 0; o < eo[a]; o++) {
			i = ei[a][o];
			add(ei1, a, o << 2 | 0, i << 3 | 0, xx_[i], yy_[i]);
			add(ei1, a, o << 2 | 1, i << 3 | 1, xx_[i], yy_[i] + n);
			add(ei1, a, o << 2 | 2, i << 3 | 2, xx_[i] + n, yy_[i]);
			add(ei1, a, o << 2 | 3, i << 3 | 3, xx_[i] + n, yy_[i] + n);
			if (cross(i, n, n + 1) < 0) {
				add(ei2, a, o << 2 | 0, i << 3 | 4, jj0[xx_[i]], yy_[i]);
				add(ei2, a, o << 2 | 1, i << 3 | 5, jj0[xx_[i]], jj1[yy_[i]]);
				add(ei2, a, o << 2 | 2, i << 3 | 6, xx_[i] + n, yy_[i]);
				add(ei2, a, o << 2 | 3, i << 3 | 7, xx_[i] + n, jj1[yy_[i]]);
			} else {
				add(ei2, a, o << 2 | 0, i << 3 | 4, xx_[i], jj1[yy_[i]]);
				add(ei2, a, o << 2 | 1, i << 3 | 5, xx_[i], yy_[i] + n);
				add(ei2, a, o << 2 | 2, i << 3 | 6, jj0[xx_[i]], jj1[yy_[i]]);
				add(ei2, a, o << 2 | 3, i << 3 | 7, jj0[xx_[i]], yy_[i] + n);
			}
		}
		et1[a] = (int *) malloc(eo[a] * 4 * sizeof *et1[a]);
		compare = compare_x1, sort(ei1[a], 0, eo[a] * 4);
		for (o = 0; o < eo[a] * 4; o++) {
			i = ei1[a][o];
			et1[a][o] = update(o == 0 ? 0 : et1[a][o - 1], 0, n_, yy1[i], 1);
		}
		compare = compare_x1, sort(ei2[a], 0, eo[a] * 4);
		et2[a] = (int *) malloc(eo[a] * 4 * sizeof *et2[a]);
		for (o = 0; o < eo[a] * 4; o++) {
			i = ei2[a][o];
			et2[a][o] = update(o == 0 ? 0 : et2[a][o - 1], 0, n_, yy1[i], (i & 3) == 0 || (i & 3) == 3 ? 1 : -1);
		}
	}
	scanf("%d", &q);
	while (q--) {
		scanf("%d%d", &a, &b), a--, b--;
		ans = 0;
		if (eo[a] < eo[b])
			for (o = 0; o < eo[a]; o++) {
				i = ei[a][o];
				if (cross(i, n, n + 1) < 0)
					ans += query_(ei1[b], et1[b], eo[b] * 4, xx_[i] + n, yy_[i], jj1[yy_[i]]) - query_(ei1[b], et1[b], eo[b] * 4, jj0[xx_[i]], yy_[i], jj1[yy_[i]]);
				else
					ans += query_(ei1[b], et1[b], eo[b] * 4, jj0[xx_[i]], jj1[yy_[i]], yy_[i] + n) - query_(ei1[b], et1[b], eo[b] * 4, xx_[i], jj1[yy_[i]], yy_[i] + n);
			}
		else
			for (o = 0; o < eo[b]; o++) {
				i = ei[b][o];
				ans += query_(ei2[a], et2[a], eo[a] * 4, xx_[i] + 1, 0, yy_[i] + 1);
				ans += query_(ei2[a], et2[a], eo[a] * 4, xx_[i] + 1, 0, yy_[i] + n + 1);
				ans += query_(ei2[a], et2[a], eo[a] * 4, xx_[i] + n + 1, 0, yy_[i] + 1);
				ans += query_(ei2[a], et2[a], eo[a] * 4, xx_[i] + n + 1, 0, yy_[i] + n + 1);
			}
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message

dragon2.c: In function 'append':
dragon2.c:21:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   21 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
dragon2.c: In function 'compare_c':
dragon2.c:37:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   37 |  int si = xx[i] < xx[u] || xx[i] == xx[u] && yy[i] < yy[u] ? -1 : 1;
      |                            ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
dragon2.c:38:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   38 |  int sj = xx[j] < xx[u] || xx[j] == xx[u] && yy[j] < yy[u] ? -1 : 1;
      |                            ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
dragon2.c: In function 'main':
dragon2.c:126:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |  scanf("%d%d", &n, &m), n_ = n * 2 + 1;
      |  ^~~~~~~~~~~~~~~~~~~~~
dragon2.c:133:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   scanf("%d%d%d", &xx[i], &yy[i], &cc[i]), cc[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.c:138:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |  scanf("%d%d%d%d", &xx[n], &yy[n], &xx[n + 1], &yy[n + 1]);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dragon2.c:189:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
dragon2.c:191:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |   scanf("%d%d", &a, &b), a--, b--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4608 KB Output is correct
2 Correct 20 ms 4692 KB Output is correct
3 Correct 80 ms 4848 KB Output is correct
4 Correct 149 ms 5032 KB Output is correct
5 Correct 67 ms 5532 KB Output is correct
6 Correct 9 ms 5204 KB Output is correct
7 Correct 8 ms 5204 KB Output is correct
8 Correct 9 ms 4652 KB Output is correct
9 Correct 8 ms 4564 KB Output is correct
10 Correct 8 ms 4656 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 52856 KB Output is correct
2 Correct 280 ms 52856 KB Output is correct
3 Correct 135 ms 52964 KB Output is correct
4 Correct 98 ms 53068 KB Output is correct
5 Correct 93 ms 59224 KB Output is correct
6 Correct 130 ms 52212 KB Output is correct
7 Correct 124 ms 52164 KB Output is correct
8 Correct 115 ms 52200 KB Output is correct
9 Correct 91 ms 52128 KB Output is correct
10 Correct 97 ms 52124 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4608 KB Output is correct
2 Correct 20 ms 4692 KB Output is correct
3 Correct 80 ms 4848 KB Output is correct
4 Correct 149 ms 5032 KB Output is correct
5 Correct 67 ms 5532 KB Output is correct
6 Correct 9 ms 5204 KB Output is correct
7 Correct 8 ms 5204 KB Output is correct
8 Correct 9 ms 4652 KB Output is correct
9 Correct 8 ms 4564 KB Output is correct
10 Correct 8 ms 4656 KB Output is correct
11 Correct 140 ms 52856 KB Output is correct
12 Correct 280 ms 52856 KB Output is correct
13 Correct 135 ms 52964 KB Output is correct
14 Correct 98 ms 53068 KB Output is correct
15 Correct 93 ms 59224 KB Output is correct
16 Correct 130 ms 52212 KB Output is correct
17 Correct 124 ms 52164 KB Output is correct
18 Correct 115 ms 52200 KB Output is correct
19 Correct 91 ms 52128 KB Output is correct
20 Correct 97 ms 52124 KB Output is correct
21 Correct 138 ms 52876 KB Output is correct
22 Correct 282 ms 52892 KB Output is correct
23 Correct 1647 ms 52956 KB Output is correct
24 Correct 2717 ms 53616 KB Output is correct
25 Correct 331 ms 54904 KB Output is correct
26 Correct 175 ms 59452 KB Output is correct
27 Correct 103 ms 58056 KB Output is correct
28 Correct 98 ms 57932 KB Output is correct
29 Correct 203 ms 60064 KB Output is correct
30 Correct 149 ms 59960 KB Output is correct
31 Correct 165 ms 60004 KB Output is correct
32 Correct 176 ms 59972 KB Output is correct
33 Correct 1450 ms 60296 KB Output is correct
34 Correct 148 ms 59980 KB Output is correct
35 Correct 146 ms 59480 KB Output is correct
36 Correct 164 ms 59360 KB Output is correct
37 Correct 174 ms 59620 KB Output is correct
38 Correct 1359 ms 60136 KB Output is correct
39 Correct 1612 ms 60088 KB Output is correct
40 Correct 1471 ms 60004 KB Output is correct
41 Correct 248 ms 60108 KB Output is correct
42 Correct 338 ms 60012 KB Output is correct
43 Correct 370 ms 60072 KB Output is correct
44 Correct 145 ms 56116 KB Output is correct
45 Correct 137 ms 56012 KB Output is correct
46 Correct 133 ms 56044 KB Output is correct
47 Correct 139 ms 56144 KB Output is correct
48 Correct 147 ms 56012 KB Output is correct
49 Correct 151 ms 56096 KB Output is correct