oj.uz

답안 #466854

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
466854 2021-08-20T20:56:30 Z rainboy 육각형 영역 (APIO21_hexagon) C++17
100 / 100
 815 ms 75116 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 * 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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 388 KB Output is correct
2 Correct 1 ms 388 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 332 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 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 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 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 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 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 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 1 ms 460 KB Output is correct
16 Correct 1 ms 332 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
20 Correct 1 ms 332 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 23 ms 1512 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 1008 KB Output is correct
6 Correct 22 ms 1868 KB Output is correct
7 Correct 80 ms 5872 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 98 ms 15996 KB Output is correct
12 Correct 100 ms 15684 KB Output is correct
13 Correct 91 ms 16176 KB Output is correct
14 Correct 141 ms 13864 KB Output is correct
15 Correct 5 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 1 ms 332 KB Output is correct

Subtask #5
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 23 ms 1564 KB Output is correct
5 Correct 4 ms 588 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 11 ms 1100 KB Output is correct
8 Correct 22 ms 1856 KB Output is correct
9 Correct 97 ms 5864 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 15920 KB Output is correct
14 Correct 113 ms 15800 KB Output is correct
15 Correct 92 ms 16116 KB Output is correct
16 Correct 163 ms 13896 KB Output is correct
17 Correct 3 ms 588 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 0 ms 332 KB Output is correct
20 Correct 214 ms 11640 KB Output is correct
21 Correct 22 ms 1680 KB Output is correct
22 Correct 9 ms 972 KB Output is correct
23 Correct 305 ms 17088 KB Output is correct
24 Correct 488 ms 28784 KB Output is correct
25 Correct 493 ms 35532 KB Output is correct
26 Correct 425 ms 19852 KB Output is correct
27 Correct 302 ms 15692 KB Output is correct
28 Correct 176 ms 8996 KB Output is correct
29 Correct 476 ms 68836 KB Output is correct
30 Correct 429 ms 71360 KB Output is correct
31 Correct 438 ms 59932 KB Output is correct
32 Correct 654 ms 54472 KB Output is correct
33 Correct 336 ms 23236 KB Output is correct
34 Correct 136 ms 12156 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 0 ms 332 KB Output is correct
37 Correct 1 ms 284 KB Output is correct

Subtask #6
19.0 / 19.0

# 결과 실행 시간 메모리 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 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 2 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 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 1 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 1 ms 332 KB Output is correct
19 Correct 21 ms 1504 KB Output is correct
20 Correct 4 ms 588 KB Output is correct
21 Correct 3 ms 460 KB Output is correct
22 Correct 12 ms 1100 KB Output is correct
23 Correct 22 ms 1884 KB Output is correct
24 Correct 78 ms 5868 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 95 ms 16000 KB Output is correct
29 Correct 103 ms 15768 KB Output is correct
30 Correct 97 ms 16108 KB Output is correct
31 Correct 172 ms 13892 KB Output is correct
32 Correct 4 ms 588 KB Output is correct
33 Correct 2 ms 460 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 22 ms 1656 KB Output is correct
36 Correct 3 ms 460 KB Output is correct
37 Correct 3 ms 460 KB Output is correct
38 Correct 21 ms 1760 KB Output is correct
39 Correct 22 ms 2036 KB Output is correct
40 Correct 113 ms 5836 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 148 ms 22080 KB Output is correct
45 Correct 139 ms 19228 KB Output is correct
46 Correct 129 ms 18832 KB Output is correct
47 Correct 140 ms 11308 KB Output is correct
48 Correct 3 ms 588 KB Output is correct
49 Correct 2 ms 460 KB Output is correct
50 Correct 0 ms 332 KB Output is correct
51 Correct 0 ms 332 KB Output is correct
52 Correct 0 ms 332 KB Output is correct
53 Correct 0 ms 332 KB Output is correct
54 Correct 0 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 0 ms 332 KB Output is correct

Subtask #7
18.0 / 18.0

# 결과 실행 시간 메모리 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 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 329 ms 16916 KB Output is correct
7 Correct 301 ms 16836 KB Output is correct
8 Correct 324 ms 20060 KB Output is correct
9 Correct 11 ms 1100 KB Output is correct
10 Correct 33 ms 3156 KB Output is correct
11 Correct 32 ms 2804 KB Output is correct
12 Correct 746 ms 45432 KB Output is correct
13 Correct 729 ms 50060 KB Output is correct
14 Correct 706 ms 45300 KB Output is correct
15 Correct 369 ms 46880 KB Output is correct
16 Correct 339 ms 40788 KB Output is correct
17 Correct 343 ms 44740 KB Output is correct
18 Correct 627 ms 56592 KB Output is correct
19 Correct 494 ms 69604 KB Output is correct
20 Correct 268 ms 49616 KB Output is correct
21 Correct 0 ms 288 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 0 ms 332 KB Output is correct
24 Correct 0 ms 284 KB Output is correct
25 Correct 0 ms 332 KB Output is correct
26 Correct 0 ms 288 KB Output is correct
27 Correct 0 ms 332 KB Output is correct
28 Correct 0 ms 332 KB Output is correct

Subtask #8
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 0 ms 332 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 1 ms 352 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 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 1512 KB Output is correct
24 Correct 5 ms 588 KB Output is correct
25 Correct 2 ms 504 KB Output is correct
26 Correct 12 ms 1100 KB Output is correct
27 Correct 22 ms 1952 KB Output is correct
28 Correct 79 ms 5864 KB Output is correct
29 Correct 4 ms 588 KB Output is correct
30 Correct 3 ms 460 KB Output is correct
31 Correct 3 ms 460 KB Output is correct
32 Correct 94 ms 15924 KB Output is correct
33 Correct 102 ms 15784 KB Output is correct
34 Correct 90 ms 16172 KB Output is correct
35 Correct 139 ms 13892 KB Output is correct
36 Correct 3 ms 588 KB Output is correct
37 Correct 2 ms 460 KB Output is correct
38 Correct 0 ms 332 KB Output is correct
39 Correct 214 ms 11656 KB Output is correct
40 Correct 21 ms 1688 KB Output is correct
41 Correct 9 ms 972 KB Output is correct
42 Correct 290 ms 17020 KB Output is correct
43 Correct 463 ms 28664 KB Output is correct
44 Correct 484 ms 35464 KB Output is correct
45 Correct 388 ms 19844 KB Output is correct
46 Correct 301 ms 15700 KB Output is correct
47 Correct 205 ms 9012 KB Output is correct
48 Correct 433 ms 68840 KB Output is correct
49 Correct 423 ms 71368 KB Output is correct
50 Correct 420 ms 59972 KB Output is correct
51 Correct 653 ms 54472 KB Output is correct
52 Correct 306 ms 23260 KB Output is correct
53 Correct 139 ms 12160 KB Output is correct
54 Correct 1 ms 332 KB Output is correct
55 Correct 22 ms 1696 KB Output is correct
56 Correct 3 ms 460 KB Output is correct
57 Correct 5 ms 460 KB Output is correct
58 Correct 24 ms 1740 KB Output is correct
59 Correct 27 ms 1996 KB Output is correct
60 Correct 98 ms 6068 KB Output is correct
61 Correct 4 ms 656 KB Output is correct
62 Correct 4 ms 548 KB Output is correct
63 Correct 3 ms 460 KB Output is correct
64 Correct 121 ms 22368 KB Output is correct
65 Correct 126 ms 19236 KB Output is correct
66 Correct 130 ms 19060 KB Output is correct
67 Correct 138 ms 11628 KB Output is correct
68 Correct 4 ms 588 KB Output is correct
69 Correct 2 ms 460 KB Output is correct
70 Correct 0 ms 332 KB Output is correct
71 Correct 368 ms 17824 KB Output is correct
72 Correct 299 ms 17624 KB Output is correct
73 Correct 377 ms 21000 KB Output is correct
74 Correct 10 ms 1200 KB Output is correct
75 Correct 44 ms 3340 KB Output is correct
76 Correct 31 ms 2852 KB Output is correct
77 Correct 780 ms 46716 KB Output is correct
78 Correct 731 ms 50540 KB Output is correct
79 Correct 815 ms 45856 KB Output is correct
80 Correct 343 ms 47064 KB Output is correct
81 Correct 350 ms 40876 KB Output is correct
82 Correct 365 ms 44976 KB Output is correct
83 Correct 707 ms 57116 KB Output is correct
84 Correct 547 ms 69824 KB Output is correct
85 Correct 280 ms 49616 KB Output is correct
86 Correct 1 ms 332 KB Output is correct
87 Correct 191 ms 11204 KB Output is correct
88 Correct 34 ms 1988 KB Output is correct
89 Correct 8 ms 844 KB Output is correct
90 Correct 286 ms 17860 KB Output is correct
91 Correct 516 ms 32264 KB Output is correct
92 Correct 515 ms 39056 KB Output is correct
93 Correct 456 ms 23288 KB Output is correct
94 Correct 312 ms 15008 KB Output is correct
95 Correct 204 ms 9792 KB Output is correct
96 Correct 469 ms 61092 KB Output is correct
97 Correct 444 ms 75116 KB Output is correct
98 Correct 428 ms 63988 KB Output is correct
99 Correct 671 ms 42380 KB Output is correct
100 Correct 310 ms 21968 KB Output is correct
101 Correct 145 ms 11804 KB Output is correct
102 Correct 0 ms 332 KB Output is correct
103 Correct 0 ms 332 KB Output is correct
104 Correct 0 ms 332 KB Output is correct
105 Correct 0 ms 332 KB Output is correct
106 Correct 0 ms 332 KB Output is correct
107 Correct 0 ms 332 KB Output is correct
108 Correct 0 ms 332 KB Output is correct
109 Correct 1 ms 332 KB Output is correct