oj.uz

Submission #685201

# Submission time Handle Problem Language Result Execution time Memory
685201 2023-01-23T16:58:40 Z rainboy Dragon 2 (JOI17_dragon2) C
15 / 100
 4000 ms 60064 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;

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] * 2)
			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 4676 KB Output is correct
2 Correct 17 ms 4792 KB Output is correct
3 Correct 73 ms 4820 KB Output is correct
4 Correct 130 ms 5908 KB Output is correct
5 Correct 60 ms 6476 KB Output is correct
6 Correct 9 ms 5332 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 9 ms 4716 KB Output is correct
9 Correct 46 ms 4756 KB Output is correct
10 Correct 49 ms 4836 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 53504 KB Output is correct
2 Correct 272 ms 53540 KB Output is correct
3 Correct 121 ms 53588 KB Output is correct
4 Correct 100 ms 53732 KB Output is correct
5 Correct 92 ms 60064 KB Output is correct
6 Correct 145 ms 52948 KB Output is correct
7 Correct 146 ms 52824 KB Output is correct
8 Correct 116 ms 52864 KB Output is correct
9 Execution timed out 4030 ms 54564 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4676 KB Output is correct
2 Correct 17 ms 4792 KB Output is correct
3 Correct 73 ms 4820 KB Output is correct
4 Correct 130 ms 5908 KB Output is correct
5 Correct 60 ms 6476 KB Output is correct
6 Correct 9 ms 5332 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 9 ms 4716 KB Output is correct
9 Correct 46 ms 4756 KB Output is correct
10 Correct 49 ms 4836 KB Output is correct
11 Correct 142 ms 53504 KB Output is correct
12 Correct 272 ms 53540 KB Output is correct
13 Correct 121 ms 53588 KB Output is correct
14 Correct 100 ms 53732 KB Output is correct
15 Correct 92 ms 60064 KB Output is correct
16 Correct 145 ms 52948 KB Output is correct
17 Correct 146 ms 52824 KB Output is correct
18 Correct 116 ms 52864 KB Output is correct
19 Execution timed out 4030 ms 54564 KB Time limit exceeded
20 Halted 0 ms 0 KB -