Submission #685202

#TimeUsernameProblemLanguageResultExecution timeMemory
685202rainboyDragon 2 (JOI17_dragon2)C11
100 / 100
2573 ms61988 KiB
#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] * 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 (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--;
      |   ^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...