oj.uz

Submission #1016943

# Submission time Handle Problem Language Result Execution time Memory
1016943 2024-07-08T15:57:37 Z Drake Hexagonal Territory (APIO21_hexagon) C++17
100 / 100
 248 ms 126132 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].p1.x, make_pair(0, 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 = (type == 0 ? S.insert(L).first : 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;
					}
				}
			}
		}
	}
	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 432 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 8 ms 3440 KB Output is correct
3 Correct 1 ms 1060 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 4 ms 1940 KB Output is correct
6 Correct 7 ms 3372 KB Output is correct
7 Correct 22 ms 9420 KB Output is correct
8 Correct 1 ms 1068 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 38 ms 27168 KB Output is correct
12 Correct 24 ms 18564 KB Output is correct
13 Correct 20 ms 15172 KB Output is correct
14 Correct 40 ms 21364 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 7 ms 3372 KB Output is correct
5 Correct 3 ms 1064 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 5 ms 1940 KB Output is correct
8 Correct 8 ms 3308 KB Output is correct
9 Correct 21 ms 9424 KB Output is correct
10 Correct 2 ms 1068 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 34 ms 26620 KB Output is correct
14 Correct 22 ms 16772 KB Output is correct
15 Correct 18 ms 15988 KB Output is correct
16 Correct 40 ms 21008 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 440 KB Output is correct
20 Correct 53 ms 27924 KB Output is correct
21 Correct 7 ms 3208 KB Output is correct
22 Correct 3 ms 1780 KB Output is correct
23 Correct 72 ms 36104 KB Output is correct
24 Correct 131 ms 59408 KB Output is correct
25 Correct 155 ms 61056 KB Output is correct
26 Correct 69 ms 37396 KB Output is correct
27 Correct 56 ms 27876 KB Output is correct
28 Correct 37 ms 16508 KB Output is correct
29 Correct 186 ms 125620 KB Output is correct
30 Correct 95 ms 64260 KB Output is correct
31 Correct 90 ms 68416 KB Output is correct
32 Correct 175 ms 96416 KB Output is correct
33 Correct 57 ms 33804 KB Output is correct
34 Correct 20 ms 12800 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 344 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 6 ms 3440 KB Output is correct
20 Correct 1 ms 1064 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 4 ms 1940 KB Output is correct
23 Correct 10 ms 3308 KB Output is correct
24 Correct 20 ms 9796 KB Output is correct
25 Correct 1 ms 1068 KB Output is correct
26 Correct 1 ms 860 KB Output is correct
27 Correct 1 ms 600 KB Output is correct
28 Correct 35 ms 26972 KB Output is correct
29 Correct 23 ms 18272 KB Output is correct
30 Correct 19 ms 16124 KB Output is correct
31 Correct 42 ms 21280 KB Output is correct
32 Correct 1 ms 672 KB Output is correct
33 Correct 1 ms 604 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 7 ms 3212 KB Output is correct
36 Correct 1 ms 860 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 7 ms 3212 KB Output is correct
39 Correct 7 ms 3564 KB Output is correct
40 Correct 25 ms 13572 KB Output is correct
41 Correct 1 ms 1068 KB Output is correct
42 Correct 1 ms 860 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 42 ms 32272 KB Output is correct
45 Correct 25 ms 17276 KB Output is correct
46 Correct 25 ms 17796 KB Output is correct
47 Correct 23 ms 13864 KB Output is correct
48 Correct 1 ms 860 KB Output is correct
49 Correct 1 ms 604 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 0 ms 436 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 82 ms 48448 KB Output is correct
7 Correct 76 ms 48856 KB Output is correct
8 Correct 84 ms 52956 KB Output is correct
9 Correct 4 ms 1932 KB Output is correct
10 Correct 10 ms 6128 KB Output is correct
11 Correct 11 ms 6392 KB Output is correct
12 Correct 164 ms 92468 KB Output is correct
13 Correct 175 ms 93332 KB Output is correct
14 Correct 145 ms 77568 KB Output is correct
15 Correct 81 ms 58696 KB Output is correct
16 Correct 96 ms 66696 KB Output is correct
17 Correct 93 ms 60992 KB Output is correct
18 Correct 222 ms 110952 KB Output is correct
19 Correct 22 ms 7252 KB Output is correct
20 Correct 123 ms 84256 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 432 KB Output is correct
28 Correct 0 ms 348 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 436 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 600 KB Output is correct
23 Correct 6 ms 3328 KB Output is correct
24 Correct 2 ms 1064 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 5 ms 1940 KB Output is correct
27 Correct 8 ms 3412 KB Output is correct
28 Correct 21 ms 9372 KB Output is correct
29 Correct 2 ms 1068 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 44 ms 27708 KB Output is correct
33 Correct 23 ms 18304 KB Output is correct
34 Correct 18 ms 15748 KB Output is correct
35 Correct 37 ms 21264 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 55 ms 27108 KB Output is correct
40 Correct 7 ms 3212 KB Output is correct
41 Correct 3 ms 1780 KB Output is correct
42 Correct 76 ms 34296 KB Output is correct
43 Correct 123 ms 58180 KB Output is correct
44 Correct 149 ms 60888 KB Output is correct
45 Correct 77 ms 37392 KB Output is correct
46 Correct 55 ms 28376 KB Output is correct
47 Correct 37 ms 17276 KB Output is correct
48 Correct 172 ms 126132 KB Output is correct
49 Correct 90 ms 62912 KB Output is correct
50 Correct 83 ms 67912 KB Output is correct
51 Correct 184 ms 97892 KB Output is correct
52 Correct 66 ms 33628 KB Output is correct
53 Correct 21 ms 12748 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 6 ms 3212 KB Output is correct
56 Correct 1 ms 948 KB Output is correct
57 Correct 1 ms 604 KB Output is correct
58 Correct 7 ms 3212 KB Output is correct
59 Correct 7 ms 3564 KB Output is correct
60 Correct 23 ms 12292 KB Output is correct
61 Correct 1 ms 1068 KB Output is correct
62 Correct 1 ms 876 KB Output is correct
63 Correct 1 ms 604 KB Output is correct
64 Correct 42 ms 33852 KB Output is correct
65 Correct 26 ms 18980 KB Output is correct
66 Correct 31 ms 18300 KB Output is correct
67 Correct 24 ms 14852 KB Output is correct
68 Correct 1 ms 856 KB Output is correct
69 Correct 1 ms 604 KB Output is correct
70 Correct 0 ms 348 KB Output is correct
71 Correct 92 ms 49384 KB Output is correct
72 Correct 97 ms 48672 KB Output is correct
73 Correct 78 ms 54088 KB Output is correct
74 Correct 4 ms 1932 KB Output is correct
75 Correct 10 ms 6904 KB Output is correct
76 Correct 11 ms 6032 KB Output is correct
77 Correct 181 ms 91080 KB Output is correct
78 Correct 183 ms 94260 KB Output is correct
79 Correct 191 ms 77636 KB Output is correct
80 Correct 87 ms 58648 KB Output is correct
81 Correct 99 ms 66728 KB Output is correct
82 Correct 116 ms 59456 KB Output is correct
83 Correct 248 ms 110004 KB Output is correct
84 Correct 24 ms 7400 KB Output is correct
85 Correct 129 ms 84508 KB Output is correct
86 Correct 1 ms 348 KB Output is correct
87 Correct 54 ms 26828 KB Output is correct
88 Correct 9 ms 3540 KB Output is correct
89 Correct 3 ms 1332 KB Output is correct
90 Correct 81 ms 36852 KB Output is correct
91 Correct 142 ms 60780 KB Output is correct
92 Correct 167 ms 66968 KB Output is correct
93 Correct 80 ms 41704 KB Output is correct
94 Correct 63 ms 28292 KB Output is correct
95 Correct 43 ms 17972 KB Output is correct
96 Correct 175 ms 117072 KB Output is correct
97 Correct 114 ms 71964 KB Output is correct
98 Correct 109 ms 68416 KB Output is correct
99 Correct 130 ms 63224 KB Output is correct
100 Correct 73 ms 32520 KB Output is correct
101 Correct 25 ms 12432 KB Output is correct
102 Correct 1 ms 348 KB Output is correct
103 Correct 0 ms 440 KB Output is correct
104 Correct 0 ms 348 KB Output is correct
105 Correct 0 ms 348 KB Output is correct
106 Correct 0 ms 348 KB Output is correct
107 Correct 0 ms 348 KB Output is correct
108 Correct 1 ms 348 KB Output is correct
109 Correct 1 ms 348 KB Output is correct