Submission #685205

#	Time	Username	Problem	Language	Result	Execution time	Memory
685205		rainboy	Dragon 2 (JOI17_dragon2)	C11	100 / 100	2644 ms	60120 KiB

dragon2

#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] * 3)
			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 (stderr)

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 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40