Submission #466854

#	Time	Username	Problem	Language	Result	Execution time	Memory
466854		rainboy	Hexagonal Territory (APIO21_hexagon)	C++17	100 / 100	815 ms	75116 KiB

hexagon

#include "hexagon.h"
#include <stdlib.h>
#include <string.h>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 200000, MD = 1000000007, V2 = 500000004, V6 = 166666668;

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int abs_(int a) { return a > 0 ? a : -a; }

unsigned int X = 12345;

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

int dx[] = { 1, 1, 0, -1, -1, 0 };
int dy[] = { 0, 1, 1, 0, -1, -1 };

int sum1(int n) {
	return (long long) n * (n + 1) % MD * V2 % MD;
}

int sum2(int n) {
	return (long long) n * (n + 1) % MD * (n * 2 + 1) % MD * V6 % MD;
}

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

long long cross(int x0, int y0, int x1, int y1, int x2, int y2) {
	return cross2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}

int hh[N], len[N], ii[N * 2], xx[N], yy[N], xx_[N * 2 * 2 * 2], yy_[N * 2 * 2], n, n_, n1;

int compare(int i, int j) {
	int i0 = i >> 1, i1 = (i0 + 1) % n, j0 = j >> 1, j1 = (j0 + 1) % n, tmp;
	long long c;

	if ((i & 1) != 0)
		tmp = i0, i0 = i1, i1 = tmp;
	if ((j & 1) != 0)
		tmp = j0, j0 = j1, j1 = tmp;
	if (yy[i0] != yy[j0])
		return yy[i0] - yy[j0];
	if (xx[i0] != xx[j0])
		return xx[i0] - xx[j0];
	if ((yy[i1] < yy[i0]) != (yy[j1] < yy[j0]))
		return yy[i1] < yy[i0] ? -1 : 1;
	c = cross(xx[i0], yy[i0], xx[i1], yy[i1], xx[j1], yy[j1]);
	if (yy[i1] < yy[i0])
		c = -c;
	return c == 0 ? 0 : (c < 0 ? -1 : 1);
}

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 zz[1 + N], ll[1 + N], rr[1 + N], ii_[1 + N], _, u_, l_, r_;

int node(int i) {
	zz[_] = rand_();
	ll[_] = rr[_] = 0;
	ii_[_] = i;
	return _++;
}

int compare_(int i, int j) {
	int i_ = (i + 1) % n, j_ = (j + 1) % n, tmp;
	long long c1, c2;

	if (i == j)
		return 0;
	if (yy[i] > yy[i_])
		tmp = i, i = i_, i_ = tmp;
	if (yy[j] > yy[j_])
		tmp = j, j = j_, j_ = tmp;
	c1 = cross(xx[i], yy[i], xx[i_], yy[i_], xx[j], yy[j]);
	c2 = cross(xx[i], yy[i], xx[i_], yy[i_], xx[j_], yy[j_]);
	if (c1 == 0 || c2 == 0 || (c1 > 0) == (c2 > 0))
		return c1 + c2 < 0 ? -1 : 1;
	c1 = cross(xx[j], yy[j], xx[j_], yy[j_], xx[i], yy[i]);
	c2 = cross(xx[j], yy[j], xx[j_], yy[j_], xx[i_], yy[i_]);
	return c1 + c2 > 0 ? -1 : 1;
}

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = compare_(ii_[u], i);
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int first(int u) { return ll[u] == 0 ? u : first(ll[u]); }
int last(int u) { return rr[u] == 0 ? u : last(rr[u]); }

int y_;

int eval(int i) {
	return xx[i] + (xx[(i + 1) % n] - xx[i]) / (yy[(i + 1) % n] - yy[i]) * (y_ - yy[i]);
}

int *ej[N * 2], eo[N * 2];

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

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

int ii1[N];

int begin_trapezoid(int i, int j) {
	int i1 = ii1[i] = n1++;

	ej[i1 << 1 | 0] = (int *) malloc(2 * sizeof *ej[i1 << 1 | 0]), eo[i1 << 1 | 0] = 0;
	ej[i1 << 1 | 1] = (int *) malloc(2 * sizeof *ej[i1 << 1 | 1]), eo[i1 << 1 | 1] = 0;
	append(i1 << 1 | 0, i1 << 1 | 1), append(i1 << 1 | 1, i1 << 1 | 0);
	xx_[(i1 << 1 | 0) << 1 | 0] = eval(i), xx_[(i1 << 1 | 0) << 1 | 1] = eval(j), yy_[i1 << 1 | 0] = y_;
	return i1;
}

int end_trapezoid(int i, int j) {
	int i1 = ii1[i];

	xx_[(i1 << 1 | 1) << 1 | 0] = eval(i), xx_[(i1 << 1 | 1) << 1 | 1] = eval(j), yy_[i1 << 1 | 1] = y_;
	return i1;
}

int intersect(int i, int j) {
	return min(xx_[i << 1 | 1], xx_[j << 1 | 1]) - max(xx_[i << 1 | 0], xx_[j << 1 | 0]) + 1;
}

int sum_trapezoid(int i, int z) {
	int j, x, y, d;

	j = i ^ 1, y = abs_(yy_[j] - yy_[i]);
	if (y == 0)
		return (long long) z * -intersect(i, j) % MD;
	d = ((xx_[j << 1 | 1] - xx_[j << 1 | 0]) - (xx_[i << 1 | 1] - xx_[i << 1 | 0])) / y;
	x = xx_[i << 1 | 1] - xx_[i << 1 | 0] + 1;
	/*
	 * sum_{h=1}^{y-1} (x + d h) (z + h)
	 * = sum_{h=1}^{y-1} d h^2 + (x + z d) h + x z
	 * = d sum2(y - 1) + (x + z d) sum1(y - 1) + x z (y - 1)
	 */
	return ((long long) sum2(y - 1) * d % MD + (long long) sum1(y - 1) * (x + z * d) % MD + (long long) + (y - 1) * x % MD * z % MD) % MD;
}

void process(int i, int j) {
	int l, r, p, q, type, hasi, hasj, a, b, c;

	split(u_, i), hasi = u_ != 0, l = l_;
	split(r_, j), hasj = u_ != 0, r = r_;
	p = l ? ii_[last(l)] : -1, q = r ? ii_[first(r)] : -1, type = p != -1 && ii1[p] != -1;
	if (!hasi && !hasj) {
		if (type == 0)
			begin_trapezoid(i, j);
		else {
			a = end_trapezoid(p, q), b = begin_trapezoid(p, i), c = begin_trapezoid(j, q);
			append(a << 1 | 1, b << 1 | 0), append(b << 1 | 0, a << 1 | 1);
			append(a << 1 | 1, c << 1 | 0), append(c << 1 | 0, a << 1 | 1);
		}
		u_ = merge(merge(l, merge(node(i), node(j))), r);
	} else if (!hasi && hasj) {
		if (type == 0)
			a = end_trapezoid(j, q), b = begin_trapezoid(i, q);
		else
			a = end_trapezoid(p, j), b = begin_trapezoid(p, i);
		append(a << 1 | 1, b << 1 | 0), append(b << 1 | 0, a << 1 | 1);
		u_ = merge(merge(l, node(i)), r);
	} else if (hasi && !hasj) {
		if (type == 0)
			a = end_trapezoid(i, q), b = begin_trapezoid(j, q);
		else
			a = end_trapezoid(p, i), b = begin_trapezoid(p, j);
		append(a << 1 | 1, b << 1 | 0), append(b << 1 | 0, a << 1 | 1);
		u_ = merge(merge(l, node(j)), r);
	} else {
		if (type == 0)
			end_trapezoid(i, j);
		else {
			a = end_trapezoid(p, i), b = end_trapezoid(j, q), c = begin_trapezoid(p, q);
			append(a << 1 | 1, c << 1 | 0), append(c << 1 | 0, a << 1 | 1);
			append(b << 1 | 1, c << 1 | 0), append(c << 1 | 0, b << 1 | 1);
		}
		u_ = merge(l, r);
	}
}

void trapezoidal_decomposition() {
	int h, i, j, x, y;

	n_ = 0, x = 0, y = 0;
	for (i = 0; i < n; i++) {
		xx[i] = x, yy[i] = y;
		x += dx[hh[i]] * len[i], y += dy[hh[i]] * len[i];
	}
	n_ = 0;
	for (i = 0; i < n; i++)
		if (yy[i] != yy[(i + 1) % n])
			ii[n_++] = i << 1 | 0, ii[n_++] = i << 1 | 1;
	sort(ii, 0, n_);
	memset(ii1, -1, n * sizeof *ii1), n1 = 0, _ = 1;
	for (h = 0; h < n_; h += 2) {
		i = ii[h] >> 1, j = ii[h + 1] >> 1;
		y_ = yy[(ii[h] & 1) == 0 ? i : (i + 1) % n], process(i, j);
	}
}

int dfs(int p, int i, int d) {
	int o, sum;

	sum = (long long) d * (xx_[i << 1 | 1] - xx_[i << 1 | 0] + 1) % MD;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			sum = (sum + dfs(i, j, d + abs_(yy_[i] - yy_[j]))) % MD;
			if ((i ^ j) == 1)
				sum = (sum + sum_trapezoid(i, d)) % MD;
			else
				sum = (sum - (long long) d * intersect(i, j)) % MD;
		}
	}
	return sum;
}

int solve() {
	int i, ans;

	trapezoidal_decomposition();
	ans = 0;
	for (i = 0; i < n1 * 2; i++)
		if (yy_[i] == 0 && xx_[i << 1 | 0] <= 0 && 0 <= xx_[i << 1 | 1]) {
			ans = dfs(-1, i, 0);
			break;
		}
	for (i = 0; i < n1 * 2; i++)
		free(ej[i]);
	return ans;
}

int draw_territory(int n_, int a, int b, vi hh_, vi len_) {
	int h, i, x, y, ans1, ans2;
	long long area2, boundary, internal;

	n = n_;
	for (i = 0; i < n; i++)
		hh[i] = hh_[i] - 1, len[i] = len_[i];
	x = 0, y = 0, area2 = 0, boundary = 0;
	for (i = 0; i < n; i++) {
		h = hh[i];
		area2 += cross2(x, y, x + dx[h] * len[i], y + dy[h] * len[i]);
		boundary += len[i];
		x += dx[h] * len[i], y += dy[h] * len[i];
	}
	if (area2 < 0)
		area2 = -area2;
	internal = (area2 - boundary) / 2 + 1;
	ans1 = (boundary + internal) % MD;
	ans2 = 0;
	for (h = 0; h < 3; h++) {
		ans2 = (ans2 + solve()) % MD;
		for (i = 0; i < n; i++)
			hh[i] = (hh[i] + 1) % 6;
	}
	if (ans2 < 0)
		ans2 += MD;
	ans2 = (long long) ans2 * V2 % MD;
	return ((long long) ans1 * a + (long long) ans2 * b) % MD;
}

Compilation message (stderr)

hexagon.cpp: In function 'void append(int, int)':
hexagon.cpp:161:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  161 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 19 / 19
• Subtask 7: 18 / 18
• Subtask 8: 16 / 16