oj.uz

Submission #728147

# Submission time Handle Problem Language Result Execution time Memory
728147 2023-04-22T03:19:43 Z SanguineChameleon Hexagonal Territory (APIO21_hexagon) C++17
100 / 100
 291 ms 119076 KB 
#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;

const long long mod = 1e9 + 7;
const long long one_half = (mod + 1) / 2;
const long long one_third = (mod + 1) / 3;

struct point {
	long long x, y;

	point() {};

	point(long long _x, long long _y): x(_x), y(_y) {};

	point operator*(long long d) {
		return point(x * d, y * d);
	}

	point operator+(point p2) {
		return point(x + p2.x, y + p2.y);
	}

	long long operator^(point p2) {
		return x * p2.y - y * p2.x;
	}
};

point dv[7] = {point(0, 0), point(0, 1), point(1, 1), point(1, 0), point(0, -1), point(-1, -1), point(-1, 0)};

struct line {
	int type, dir, len;
	point p1, p2;
	int id;

	line() {};

	line(int _type, int _dir, point _p1, point _p2, int _id): type(_type), dir(_dir), p1(_p1), p2(_p2), id(_id) {
		len = p2.x - p1.x + 1;
	};

	long long calc() {
		long long Ly = p1.y;
		long long Ry = p1.y + (dir == 1 ? 0 : len - 1);
		if (type == 1) {
			Ly = 1 - Ly;
			Ry = 1 - Ry;
		}
		return (Ly + Ry) % mod * len % mod * one_half % mod;
	}

	long long eval_x(long long x) {
		if (dir == 1) {
			return p1.y;
		}
		else {
			return p1.y + (x - p1.x);
		}
	}

	void shorten(long long left_x, long long right_x) {
		long long v1 = eval_x(left_x);
		long long v2 = eval_x(right_x);
		p1 = point(left_x, v1);
		p2 = point(right_x, v2);
	}
};

bool operator<(line L1, line L2) {
	int max_x = max(L1.p1.x, L2.p1.x);
	int v1 = L1.eval_x(max_x);
	int v2 = L2.eval_x(max_x);
	if (v1 != v2) {
		return v1 < v2;
	}
	else {
		return L1.type < L2.type;
	}
};

struct column {
	long long x, left_y, right_y, min_dist, left_min, right_min;

	column() {};

	column(long long _x, long long _left_y, long long _right_y): x(_x), left_y(_left_y), right_y(_right_y) {};

	column(long long _x, long long _left_y, long long _right_y, long long _min_dist, long long _left_min, long long _right_min): x(_x), left_y(_left_y), right_y(_right_y), min_dist(_min_dist), left_min(_left_min), right_min(_right_min) {};

	long long calc(long long A, long long B) {
		long long left_len = (left_min - left_y) % mod;
		long long mid_len = (right_min - left_min + 1) % mod;
		long long right_len = (right_y - right_min) % mod;
		long long A_sum = (right_y - left_y + 1) % mod;
		long long B_sum = (min_dist * mid_len % mod + (min_dist + 1 + min_dist + left_len) * left_len % mod * one_half % mod + (min_dist + 1 + min_dist + right_len) * right_len % mod * one_half % mod) % mod;
		return (A_sum * A + B_sum * B) % mod;
	}
};

struct comp {
	line bottom, top;
	int left_x, right_x, len;
	column left_col, right_col;
	long long sum;

	comp() {};

	comp(line _bottom, line _top, int _left_x, int _right_x): bottom(_bottom), top(_top), left_x(_left_x), right_x(_right_x) {
		bottom.shorten(left_x, right_x);
		top.shorten(left_x, right_x);
		len = right_x - left_x + 1;
	}

	long long calc() {
		long long Ly = top.p1.y - bottom.p1.y + 1;
		long long Ry = top.p2.y - bottom.p2.y + 1;
		return (Ly + Ry) % mod * len % mod * one_half % mod;
	}
};

column move_right_one(column Col1, column Col2) {
	if (Col2.left_y > Col1.right_min + 1) {
		Col2.min_dist = Col2.left_y - (Col1.right_min + 1) + (Col1.min_dist + 1);
		Col2.left_min = Col2.left_y;
		Col2.right_min = Col2.left_y;
		return Col2;
	}
	if (Col2.right_y < Col1.left_min) {
		Col2.min_dist = Col1.left_min - Col2.right_y + (Col1.min_dist + 1);
		Col2.left_min = Col2.right_y;
		Col2.right_min = Col2.right_y;
		return Col2;
	}
	Col2.min_dist = Col1.min_dist + 1;
	Col2.left_min = max(Col2.left_y, Col1.left_min);
	Col2.right_min = min(Col2.right_y, Col1.right_min + 1);
	return Col2;
}

column move_left_one(column Col1, column Col2) {
	if (Col2.left_y > Col1.right_min) {
		Col2.min_dist = Col2.left_y - Col1.right_min + (Col1.min_dist + 1);
		Col2.left_min = Col2.left_y;
		Col2.right_min = Col2.left_y;
		return Col2;
	}
	if (Col2.right_y < Col1.left_min - 1) {
		Col2.min_dist = (Col1.left_min - 1) - Col2.right_y + (Col1.min_dist + 1);
		Col2.left_min = Col2.right_y;
		Col2.right_min = Col2.right_y;
		return Col2;
	}
	Col2.min_dist = Col1.min_dist + 1;
	Col2.left_min = max(Col2.left_y, Col1.left_min - 1);
	Col2.right_min = min(Col2.right_y, Col1.right_min);
	return Col2;
}

long long calc_inc(long long L, long long R, long long W) {
	if (L == R) {
		return W * L % mod * (L + 1) % mod * one_half % mod;
	}
	if (R == 0) {
		return 0;
	}
	L = max(L, 1LL);
	long long sum1 = (L + R) % mod * (R - L + 1) % mod * one_half % mod;
	long long sum2 = ((R * (R + 1) % mod * (R * 2 + 1) % mod) + (mod - (L - 1) * L % mod * (L * 2 - 1) % mod)) % mod * one_half % mod * one_third % mod;
	return (sum1 + sum2) % mod * one_half % mod;
}

pair<long long, column> move_right(column Col, line bottom, line top, long long left_x, long long right_x, long long A, long long B) {
	long long width = right_x - left_x + 1;
	long long height_left = top.eval_x(left_x) - bottom.eval_x(left_x) + 1;
	long long height_right = top.eval_x(right_x) - bottom.eval_x(right_x) + 1;
	long long nxt_left_y = bottom.eval_x(right_x);
	long long nxt_right_y = top.eval_x(right_x);
	long long nxt_left_min = max(Col.left_min, nxt_left_y);
	long long nxt_right_min = min(Col.right_min + right_x - left_x, nxt_right_y);
	long long nxt_min_dist = Col.min_dist + right_x - left_x;
	long long top_height_left = Col.right_y - Col.right_min;
	long long top_height_right = nxt_right_y - nxt_right_min;
	long long bottom_height_left = Col.left_min - Col.left_y;
	long long bottom_height_right = nxt_left_min - nxt_left_y;
	long long B_sum_top = calc_inc(top_height_right, top_height_left, width);
	long long B_sum_bottom = calc_inc(bottom_height_right, bottom_height_left, width);
	long long A_sum = (height_left + height_right) % mod * width % mod * one_half % mod;
	long long B_off1 = A_sum * Col.min_dist % mod;
	long long B_off2 = 0;
	if (height_left == height_right) {
		B_off2 = height_left * (width - 1) % mod * width % mod * one_half % mod;
	}
	if (height_left < height_right) {
		long long diff = (height_right - height_left) % mod;
		long long rect = height_left * (width - 1) % mod * width % mod * one_half % mod;
		long long tri = diff * (diff + 1) % mod * (diff * 2 + 1) % mod * one_half % mod * one_third % mod;
		B_off2 = (rect + tri) % mod;
	}
	if (height_left > height_right) {
		swap(height_left, height_right);
		long long diff = (height_right - height_left) % mod;
		long long rect = height_left * (width - 1) % mod * width % mod * one_half % mod;
		long long tri = diff * (diff + 1) % mod * (diff * 2 + 1) % mod * one_half % mod * one_third % mod;
		B_off2 = ((width - 1) * A_sum % mod + (mod - (rect + tri) % mod)) % mod;
		swap(height_left, height_right);
	}
	long long res = (A_sum * A + (B_sum_top + B_sum_bottom + B_off1 + B_off2) % mod * B) % mod;
	return make_pair(res, column(right_x, nxt_left_y, nxt_right_y, nxt_min_dist, nxt_left_min, nxt_right_min));
}

pair<long long, column> move_left(column Col, line bottom, line top, long long right_x, long long left_x, long long A, long long B) {
	Col.x = -Col.x;
	Col.left_y = -Col.left_y;
	Col.right_y = -Col.right_y;
	swap(Col.left_y, Col.right_y);
	Col.left_min = -Col.left_min;
	Col.right_min = -Col.right_min;
	swap(Col.left_min, Col.right_min);
	left_x = -left_x;
	right_x = -right_x;
	swap(left_x, right_x);
	bottom.p1.x = -bottom.p1.x;
	bottom.p1.y = -bottom.p1.y;
	bottom.p2.x = -bottom.p2.x;
	bottom.p2.y = -bottom.p2.y;
	swap(bottom.p1, bottom.p2);
	top.p1.x = -top.p1.x;
	top.p1.y = -top.p1.y;
	top.p2.x = -top.p2.x;
	top.p2.y = -top.p2.y;
	swap(top.p1, top.p2);
	swap(bottom, top);
	auto p_right = move_right(Col, bottom, top, left_x, right_x, A, B);
	p_right.second.left_y = -p_right.second.left_y;
	p_right.second.right_y = -p_right.second.right_y;
	swap(p_right.second.left_y, p_right.second.right_y);
	p_right.second.left_min = -p_right.second.left_min;
	p_right.second.right_min = -p_right.second.right_min;
	swap(p_right.second.left_min, p_right.second.right_min);
	return p_right;
}

vector<comp> comps;
vector<vector<int>> adj;

void dfs(int u, int par, long long A, long long B) {
	for (auto v: adj[u]) {
		if (v == par) {
			continue;
		}
		if (comps[u].right_x + 1 == comps[v].left_x) {
			comps[v].left_col = move_right_one(comps[u].right_col, column(comps[v].left_x, comps[v].bottom.p1.y, comps[v].top.p1.y));
			auto p_right = move_right(comps[v].left_col, comps[v].bottom, comps[v].top, comps[v].left_x, comps[v].right_x, A, B);
			comps[v].sum = p_right.first;
			comps[v].right_col = p_right.second;
		}
		else {
			comps[v].right_col = move_left_one(comps[u].left_col, column(comps[v].right_x, comps[v].bottom.p2.y, comps[v].top.p2.y));
			auto p_left = move_left(comps[v].right_col, comps[v].bottom, comps[v].top, comps[v].right_x, comps[v].left_x, A, B);
			comps[v].sum = p_left.first;
			comps[v].left_col = p_left.second;
		}
		dfs(v, u, A, B);
	}
}

int draw_territory(int N, int A, int B, vector<int> D, vector<int> L) {
	long long area = 0;
	point cur = point(0, 0);
	vector<point> poly(N);
	for (int i = 0; i < N; i++) {
		poly[i] = cur;
		cur = cur + (dv[D[i]] * L[i]);
	}
	for (int i = 0; i < N; i++) {
		area += poly[i] ^ poly[(i + 1) % N];
	}
	if (area < 0) {
		reverse(D.begin(), D.end());
		for (int i = 0; i < N; i++) {
			if (D[i] <= 3) {
				D[i] += 3;
			}
			else {
				D[i] -= 3;
			}
		}
		reverse(L.begin(), L.end());
		cur = point(0, 0);
		for (int i = 0; i < N; i++) {
			poly[i] = cur;
			cur = cur + (dv[D[i]] * L[i]);
		}
	}
	vector<line> lines;
	vector<int> prv_x;
	for (int i = 0; i < N; i++) {
		point prv = poly[(i + (N - 1)) % N];
		point cur = poly[i];
		point nxt1 = poly[(i + 1) % N];
		point nxt2 = poly[(i + 2) % N];
		if (cur.x < nxt1.x) {
			point p1 = cur;
			point p2 = nxt1;
			int dir = (cur.y == nxt1.y ? 1 : 2);
			if (prv.x < cur.x) {
				if (dir == 1) {
					p1 = p1 + point(1, 0);
				}
				else {
					p1 = p1 + point(1, 1);
				}
			}
			if (prv.x == cur.x && prv.y < cur.y) {
				if (dir == 1) {
					p1 = p1 + point(1, 0);
				}
				else {
					p1 = p1 + point(1, 1);
				}
			}
			if (nxt1.x == nxt2.x && nxt1.y > nxt2.y) {
				if (dir == 1) {
					p2 = p2 + point(-1, 0);
				}
				else {
					p2 = p2 + point(-1, -1);
				}
			}
			if (p1.x <= p2.x) {
				lines.emplace_back(1, dir, p1, p2, lines.size());
				prv_x.push_back(p1.x);
			}
		}
		if (cur.x > nxt1.x) {
			point p1 = nxt1;
			point p2 = cur;
			int dir = (cur.y == nxt1.y ? 1 : 2);
			if (prv.x > cur.x) {
				if (dir == 1) {
					p2 = p2 + point(-1, 0);
				}
				else {
					p2 = p2 + point(-1, -1);
				}
			}
			if (prv.x == cur.x && prv.y > cur.y) {
				if (dir == 1) {
					p2 = p2 + point(-1, 0);
				}
				else {
					p2 = p2 + point(-1, -1);
				}
			}
			if (nxt1.x == nxt2.x && nxt1.y < nxt2.y) {
				if (dir == 1) {
					p1 = p1 + point(1, 0);
				}
				else {
					p1 = p1 + point(1, 1);
				}
			}
			if (p1.x <= p2.x) {
				lines.emplace_back(2, dir, p1, p2, lines.size());
				prv_x.push_back(p1.x);
			}
		}
	}
	vector<pair<int, pair<int, int>>> events;
	for (int i = 0; i < (int)lines.size(); i++) {
		events.push_back(make_pair(lines[i].p1.x - 1, make_pair(2, i)));
		events.push_back(make_pair(lines[i].p2.x, make_pair(1, i)));
	}
	sort(events.begin(), events.end());
	set<line, less<>> S;
	for (auto e: events) {
		int cur_x = e.first;
		int type = e.second.first;
		line L = lines[e.second.second];
		auto it = S.lower_bound(L);
		if (type == 1) {
			if (it->type == 1 && next(it) != S.end()) {
				auto bottom = it;
				auto top = next(it);
				if (prv_x[bottom->id] <= cur_x && prv_x[top->id] <= cur_x) {
					comps.emplace_back(*bottom, *top, prv_x[bottom->id], cur_x);
					prv_x[bottom->id] = cur_x + 1;
					prv_x[top->id] = cur_x + 1;
				}
			}
			if (it->type == 2 && it != S.begin()) {
				auto bottom = prev(it);
				auto top = it;
				if (prv_x[bottom->id] <= cur_x && prv_x[top->id] <= cur_x) {
					comps.emplace_back(*bottom, *top, prv_x[bottom->id], cur_x);
					prv_x[bottom->id] = cur_x + 1;
					prv_x[top->id] = cur_x + 1;
				}
			}
			S.erase(it);
		}
		if (type == 2) {
			if (it != S.end() && it != S.begin()) {
				auto bottom = prev(it);
				auto top = it;
				if (bottom->type == 1 && top->type == 2) {
					if (prv_x[bottom->id] <= cur_x && prv_x[top->id] <= cur_x) {
						comps.emplace_back(*bottom, *top, prv_x[bottom->id], cur_x);
						prv_x[bottom->id] = cur_x + 1;
						prv_x[top->id] = cur_x + 1;
					}
				}
			}
			S.insert(L);
		}
	}
	adj.resize(comps.size());
	events.clear();
	for (int i = 0; i < (int)comps.size(); i++) {
		events.push_back(make_pair(comps[i].right_x + 1, make_pair(comps[i].bottom.p2.y, i)));
		events.push_back(make_pair(comps[i].left_x, make_pair(comps[i].bottom.p1.y, -i - 1)));
	}
	sort(events.begin(), events.end());
	int lid = -1;
	int rid = -1;
	for (auto e: events) {
		if (e.second.second >= 0) {
			lid = e.second.second;
		}
		else {
			rid = -e.second.second - 1;
		}
		if (lid >= 0 && rid >= 0 && comps[lid].right_x + 1 == comps[rid].left_x && max(comps[lid].bottom.p2.y, comps[rid].bottom.p1.y) <= min(comps[lid].top.p2.y + 1, comps[rid].top.p1.y)) {
			adj[lid].push_back(rid);
			adj[rid].push_back(lid);
		}
	}
	int root = -1;
	for (int i = 0; i < (int)comps.size(); i++) {
		auto C = comps[i];
		if (C.left_x <= 0 && 0 <= C.right_x) {
			int left_y = C.bottom.eval_x(0);
			int right_y = C.top.eval_x(0);
			if (left_y <= 0 && 0 <= right_y) {
				column mid_col(0, left_y, right_y, 0, 0, 0);
				auto p_left = move_left(mid_col, C.bottom, C.top, 0, C.left_x, A, B);
				auto p_right = move_right(mid_col, C.bottom, C.top, 0, C.right_x, A, B);
				comps[i].left_col = p_left.second;
				comps[i].right_col = p_right.second;
				comps[i].sum = (p_left.first + p_right.first + mod - mid_col.calc(A, B)) % mod;
				root = i;
				break;
			}
		}
	}
	dfs(root, -1, A, B);
	long long res = 0;
	for (auto C: comps) {
		res += C.sum;
		res %= mod;
	}
	return res;
}

Subtask #1
3.0 / 3.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 560 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 432 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 300 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 8 ms 3176 KB Output is correct
3 Correct 2 ms 1128 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 5 ms 1912 KB Output is correct
6 Correct 9 ms 3252 KB Output is correct
7 Correct 29 ms 9036 KB Output is correct
8 Correct 2 ms 904 KB Output is correct
9 Correct 1 ms 776 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 47 ms 23428 KB Output is correct
12 Correct 34 ms 16244 KB Output is correct
13 Correct 34 ms 13944 KB Output is correct
14 Correct 47 ms 19964 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 1 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 8 ms 3176 KB Output is correct
5 Correct 2 ms 1032 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 7 ms 1876 KB Output is correct
8 Correct 9 ms 3276 KB Output is correct
9 Correct 27 ms 9220 KB Output is correct
10 Correct 2 ms 904 KB Output is correct
11 Correct 2 ms 736 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 46 ms 23348 KB Output is correct
14 Correct 33 ms 16232 KB Output is correct
15 Correct 25 ms 13948 KB Output is correct
16 Correct 49 ms 20024 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 304 KB Output is correct
20 Correct 82 ms 24872 KB Output is correct
21 Correct 9 ms 3180 KB Output is correct
22 Correct 4 ms 1772 KB Output is correct
23 Correct 97 ms 33204 KB Output is correct
24 Correct 164 ms 54244 KB Output is correct
25 Correct 186 ms 58168 KB Output is correct
26 Correct 98 ms 35652 KB Output is correct
27 Correct 78 ms 26792 KB Output is correct
28 Correct 50 ms 16456 KB Output is correct
29 Correct 236 ms 119076 KB Output is correct
30 Correct 122 ms 58536 KB Output is correct
31 Correct 141 ms 63460 KB Output is correct
32 Correct 264 ms 93260 KB Output is correct
33 Correct 77 ms 30248 KB Output is correct
34 Correct 27 ms 12124 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 212 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 428 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 428 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 8 ms 3176 KB Output is correct
20 Correct 2 ms 1124 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 4 ms 1908 KB Output is correct
23 Correct 8 ms 3308 KB Output is correct
24 Correct 27 ms 8996 KB Output is correct
25 Correct 2 ms 992 KB Output is correct
26 Correct 2 ms 776 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 46 ms 23440 KB Output is correct
29 Correct 32 ms 16352 KB Output is correct
30 Correct 27 ms 13928 KB Output is correct
31 Correct 50 ms 19940 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Correct 2 ms 596 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 10 ms 3308 KB Output is correct
36 Correct 2 ms 776 KB Output is correct
37 Correct 1 ms 596 KB Output is correct
38 Correct 8 ms 3180 KB Output is correct
39 Correct 9 ms 3404 KB Output is correct
40 Correct 31 ms 11832 KB Output is correct
41 Correct 2 ms 904 KB Output is correct
42 Correct 1 ms 776 KB Output is correct
43 Correct 1 ms 596 KB Output is correct
44 Correct 55 ms 29936 KB Output is correct
45 Correct 36 ms 16680 KB Output is correct
46 Correct 35 ms 16120 KB Output is correct
47 Correct 29 ms 12952 KB Output is correct
48 Correct 1 ms 780 KB Output is correct
49 Correct 1 ms 596 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 1 ms 212 KB Output is correct
55 Correct 1 ms 300 KB Output is correct
56 Correct 1 ms 212 KB Output is correct
57 Correct 0 ms 212 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 119 ms 45892 KB Output is correct
7 Correct 111 ms 45944 KB Output is correct
8 Correct 127 ms 47168 KB Output is correct
9 Correct 4 ms 1900 KB Output is correct
10 Correct 12 ms 6000 KB Output is correct
11 Correct 13 ms 6000 KB Output is correct
12 Correct 212 ms 88072 KB Output is correct
13 Correct 222 ms 88224 KB Output is correct
14 Correct 196 ms 74460 KB Output is correct
15 Correct 116 ms 55844 KB Output is correct
16 Correct 140 ms 61320 KB Output is correct
17 Correct 142 ms 54968 KB Output is correct
18 Correct 291 ms 103116 KB Output is correct
19 Correct 37 ms 7120 KB Output is correct
20 Correct 152 ms 82120 KB Output is correct
21 Correct 1 ms 300 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 0 ms 300 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 424 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 424 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 516 KB Output is correct
17 Correct 1 ms 436 KB Output is correct
18 Correct 1 ms 424 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 296 KB Output is correct
21 Correct 1 ms 300 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 9 ms 3148 KB Output is correct
24 Correct 2 ms 1032 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 5 ms 1884 KB Output is correct
27 Correct 11 ms 3308 KB Output is correct
28 Correct 34 ms 9048 KB Output is correct
29 Correct 3 ms 904 KB Output is correct
30 Correct 1 ms 776 KB Output is correct
31 Correct 1 ms 596 KB Output is correct
32 Correct 48 ms 23364 KB Output is correct
33 Correct 32 ms 16372 KB Output is correct
34 Correct 25 ms 13860 KB Output is correct
35 Correct 49 ms 19984 KB Output is correct
36 Correct 1 ms 684 KB Output is correct
37 Correct 1 ms 596 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 79 ms 24588 KB Output is correct
40 Correct 8 ms 3200 KB Output is correct
41 Correct 4 ms 1784 KB Output is correct
42 Correct 118 ms 32960 KB Output is correct
43 Correct 157 ms 53816 KB Output is correct
44 Correct 169 ms 57688 KB Output is correct
45 Correct 132 ms 35232 KB Output is correct
46 Correct 81 ms 26628 KB Output is correct
47 Correct 50 ms 16352 KB Output is correct
48 Correct 230 ms 118644 KB Output is correct
49 Correct 118 ms 58096 KB Output is correct
50 Correct 134 ms 63100 KB Output is correct
51 Correct 238 ms 92804 KB Output is correct
52 Correct 80 ms 30016 KB Output is correct
53 Correct 27 ms 12104 KB Output is correct
54 Correct 1 ms 212 KB Output is correct
55 Correct 9 ms 3284 KB Output is correct
56 Correct 2 ms 776 KB Output is correct
57 Correct 1 ms 596 KB Output is correct
58 Correct 8 ms 3248 KB Output is correct
59 Correct 9 ms 3404 KB Output is correct
60 Correct 32 ms 11900 KB Output is correct
61 Correct 2 ms 904 KB Output is correct
62 Correct 2 ms 776 KB Output is correct
63 Correct 1 ms 596 KB Output is correct
64 Correct 57 ms 29928 KB Output is correct
65 Correct 40 ms 16612 KB Output is correct
66 Correct 34 ms 16020 KB Output is correct
67 Correct 29 ms 12972 KB Output is correct
68 Correct 2 ms 780 KB Output is correct
69 Correct 1 ms 556 KB Output is correct
70 Correct 1 ms 304 KB Output is correct
71 Correct 121 ms 45500 KB Output is correct
72 Correct 109 ms 45636 KB Output is correct
73 Correct 117 ms 46852 KB Output is correct
74 Correct 4 ms 1880 KB Output is correct
75 Correct 13 ms 6128 KB Output is correct
76 Correct 15 ms 6000 KB Output is correct
77 Correct 206 ms 87692 KB Output is correct
78 Correct 217 ms 87804 KB Output is correct
79 Correct 193 ms 74036 KB Output is correct
80 Correct 112 ms 55368 KB Output is correct
81 Correct 125 ms 60888 KB Output is correct
82 Correct 127 ms 54744 KB Output is correct
83 Correct 269 ms 102672 KB Output is correct
84 Correct 32 ms 6752 KB Output is correct
85 Correct 161 ms 81844 KB Output is correct
86 Correct 1 ms 340 KB Output is correct
87 Correct 68 ms 23868 KB Output is correct
88 Correct 10 ms 3436 KB Output is correct
89 Correct 3 ms 1184 KB Output is correct
90 Correct 105 ms 33184 KB Output is correct
91 Correct 167 ms 56640 KB Output is correct
92 Correct 180 ms 61072 KB Output is correct
93 Correct 95 ms 40572 KB Output is correct
94 Correct 77 ms 25864 KB Output is correct
95 Correct 51 ms 17012 KB Output is correct
96 Correct 213 ms 109396 KB Output is correct
97 Correct 124 ms 67404 KB Output is correct
98 Correct 113 ms 64208 KB Output is correct
99 Correct 158 ms 57388 KB Output is correct
100 Correct 111 ms 30872 KB Output is correct
101 Correct 30 ms 11892 KB Output is correct
102 Correct 1 ms 300 KB Output is correct
103 Correct 1 ms 212 KB Output is correct
104 Correct 0 ms 212 KB Output is correct
105 Correct 1 ms 212 KB Output is correct
106 Correct 1 ms 212 KB Output is correct
107 Correct 1 ms 212 KB Output is correct
108 Correct 1 ms 212 KB Output is correct
109 Correct 0 ms 212 KB Output is correct