oj.uz

Submission #466852

# Submission time Handle Problem Language Result Execution time Memory
466852 2021-08-20T20:54:00 Z rainboy Hexagonal Territory (APIO21_hexagon) C++17
51 / 100
 324 ms 42908 KB 
#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], eo[N];

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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 0 ms 332 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 252 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 412 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 0 ms 332 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 21 ms 1604 KB Output is correct
3 Correct 4 ms 588 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 11 ms 1132 KB Output is correct
6 Correct 21 ms 1868 KB Output is correct
7 Correct 81 ms 5996 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 3 ms 564 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 98 ms 16112 KB Output is correct
12 Correct 100 ms 15916 KB Output is correct
13 Correct 96 ms 16412 KB Output is correct
14 Correct 143 ms 14112 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 2 ms 460 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 0 ms 332 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 20 ms 1608 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 12 ms 1076 KB Output is correct
8 Correct 22 ms 1868 KB Output is correct
9 Correct 76 ms 6028 KB Output is correct
10 Correct 4 ms 588 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 96 ms 16100 KB Output is correct
14 Correct 101 ms 15968 KB Output is correct
15 Correct 91 ms 16272 KB Output is correct
16 Correct 140 ms 14076 KB Output is correct
17 Correct 3 ms 588 KB Output is correct
18 Correct 3 ms 460 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 214 ms 12280 KB Output is correct
21 Correct 21 ms 1740 KB Output is correct
22 Correct 9 ms 940 KB Output is correct
23 Correct 289 ms 17780 KB Output is correct
24 Runtime error 174 ms 40820 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 276 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 20 ms 1552 KB Output is correct
20 Correct 4 ms 672 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 11 ms 1088 KB Output is correct
23 Correct 23 ms 1868 KB Output is correct
24 Correct 76 ms 6008 KB Output is correct
25 Correct 4 ms 588 KB Output is correct
26 Correct 3 ms 460 KB Output is correct
27 Correct 2 ms 460 KB Output is correct
28 Correct 98 ms 16200 KB Output is correct
29 Correct 126 ms 15960 KB Output is correct
30 Correct 92 ms 16288 KB Output is correct
31 Correct 140 ms 14008 KB Output is correct
32 Correct 6 ms 588 KB Output is correct
33 Correct 2 ms 416 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 25 ms 1696 KB Output is correct
36 Correct 3 ms 588 KB Output is correct
37 Correct 2 ms 460 KB Output is correct
38 Correct 22 ms 1752 KB Output is correct
39 Correct 23 ms 2008 KB Output is correct
40 Correct 75 ms 5948 KB Output is correct
41 Correct 4 ms 588 KB Output is correct
42 Correct 3 ms 460 KB Output is correct
43 Correct 2 ms 460 KB Output is correct
44 Correct 128 ms 22304 KB Output is correct
45 Correct 124 ms 19252 KB Output is correct
46 Correct 137 ms 19124 KB Output is correct
47 Correct 158 ms 11552 KB Output is correct
48 Correct 5 ms 588 KB Output is correct
49 Correct 3 ms 460 KB Output is correct
50 Correct 0 ms 332 KB Output is correct
51 Correct 1 ms 332 KB Output is correct
52 Correct 0 ms 332 KB Output is correct
53 Correct 0 ms 284 KB Output is correct
54 Correct 1 ms 332 KB Output is correct
55 Correct 0 ms 332 KB Output is correct
56 Correct 0 ms 332 KB Output is correct
57 Correct 1 ms 332 KB Output is correct

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 317 ms 17712 KB Output is correct
7 Correct 313 ms 17612 KB Output is correct
8 Correct 324 ms 20904 KB Output is correct
9 Correct 10 ms 1228 KB Output is correct
10 Correct 34 ms 3276 KB Output is correct
11 Correct 36 ms 2888 KB Output is correct
12 Runtime error 235 ms 42908 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 288 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 20 ms 1520 KB Output is correct
24 Correct 4 ms 588 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 13 ms 1100 KB Output is correct
27 Correct 24 ms 1992 KB Output is correct
28 Correct 76 ms 6004 KB Output is correct
29 Correct 5 ms 588 KB Output is correct
30 Correct 4 ms 460 KB Output is correct
31 Correct 2 ms 460 KB Output is correct
32 Correct 98 ms 16292 KB Output is correct
33 Correct 101 ms 15980 KB Output is correct
34 Correct 94 ms 16280 KB Output is correct
35 Correct 141 ms 14096 KB Output is correct
36 Correct 4 ms 588 KB Output is correct
37 Correct 2 ms 460 KB Output is correct
38 Correct 0 ms 292 KB Output is correct
39 Correct 216 ms 12296 KB Output is correct
40 Correct 23 ms 1756 KB Output is correct
41 Correct 12 ms 1024 KB Output is correct
42 Correct 302 ms 17876 KB Output is correct
43 Runtime error 182 ms 40816 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -