제출 #728099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
728099		SanguineChameleon	육각형 영역 (APIO21_hexagon)	C++17	66 / 100	2078 ms	97484 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef KAMIRULEZ
	const bool local = true;
	const int subtask = 6;
#else
	const bool local = false;
	const int subtask = -1;
#endif

const long long mod = 1e9 + 7;
const long long one_half = (mod + 1) / 2;
const long long one_third = (mod + 1) / 3;
const int dx[7] = {0, 0, 1, 1, 0, -1, -1};
const int dy[7] = {0, 1, 1, 0, -1, -1, 0};

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)};

ostream& operator<<(ostream &out, point p) {
	out << "(" << p.x << "," << p.y << ")";
	return out;
}

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);
	}
};

ostream& operator<<(ostream &out, line L) {
	if (L.type == 1) {
		out << "(bottom,";
	}
	else {
		out << "(top,";
	}
	out << L.p1 << "," << L.p2 << ")";
	return out;
}

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;
	}
};

ostream& operator<<(ostream &out, column Col) {
	out << "(" << Col.x << ",(" << Col.left_y << "," << Col.right_y << "),min=" << Col.min_dist << ",(" << Col.left_min << "," << Col.right_min << "))";
	return out;
}

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;
	}
};

ostream& operator<<(ostream &out, comp C) {
	out << "(" << C.bottom << "," << C.top << ",(" << C.left_x << "," << C.right_x << "))";
	return out;
}

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;
}

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 A_sum = 0;
	long long B_sum = 0;
	long long B_off1 = 0;
	long long B_off2 = 0;
	column cur = Col;
	for (int x = left_x; x <= right_x; x++) {
		A_sum += cur.calc(1, 0);
		A_sum %= mod;
		B_off1 += cur.calc(1, 0) * Col.min_dist % mod;
		B_off1 %= mod;
		B_off2 += cur.calc(1, 0) * (cur.min_dist - Col.min_dist) % mod;
		B_off2 %= mod;
		long long tmp = cur.min_dist;
		cur.min_dist = 0;
		B_sum += cur.calc(0, 1);
		B_sum %= mod;
		cur.min_dist = tmp;
		if (x == right_x) {
			break;
		}
		column nxt = move_right_one(cur, column(x + 1, bottom.eval_x(x + 1), top.eval_x(x + 1)));
		cur = nxt;
	}
	long long res = (A_sum * A + (B_sum + B_off1 + B_off2) % mod * B) % mod;
	long long _left_y = bottom.eval_x(right_x);
	long long _right_y = top.eval_x(right_x);
	long long _left_min = max(Col.left_min, _left_y);
	long long _right_min = min(Col.right_min + right_x - left_x, _right_y);
	long long _min_dist = Col.min_dist + right_x - left_x;
	return make_pair(res, column(right_x, _left_y, _right_y, _min_dist, _left_min, _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) {
	if (N == 3 && (!local || subtask == 1 || subtask == 2)) {
		int len = L[0] + 1;
		long long A_sum = 1LL * len * (len + 1) % mod * one_half % mod;
		long long B_sum = 1LL * len * (len - 1) % mod * one_half % mod + (len - 1) * len % mod * (len * 2 - 1) % mod * one_half % mod * one_third % mod;
		return (A_sum * A + B_sum * B) % mod;
	}
	long long L_sum = 0;
	for (int i = 0; i < N; i++) {
		L_sum += L[i];
	}
	if (L_sum <= 2000 && (!local || subtask == 3)) {
		vector<vector<bool>> border(4069, vector<bool>(4069, false));
		vector<vector<int>> dist(4069, vector<int>(4069, -1));
		int cx = 0;
		int cy = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < L[i]; j++) {
				cx += dx[D[i]];
				cy += dy[D[i]];
				border[cx + 2023][cy + 2023] = true;
			}
		}
		deque<pair<int, int>> q = {{0, 0}};
		dist[0][0] = -2;
		while (!q.empty()) {
			cx = q.front().first;
			cy = q.front().second;
			q.pop_front();
			for (int d = 1; d <= 6; d++) {
				int nx = cx + dx[d];
				int ny = cy + dy[d];
				if (0 <= nx && nx < 4069 && 0 <= ny && ny < 4069 && !border[nx][ny] && dist[nx][ny] == -1) {
					dist[nx][ny] = -2;
					q.push_back({nx, ny});
				}
			}
		}
		q.push_back({2023, 2023});
		dist[2023][2023] = 0;
		long long res = 0;
		while (!q.empty()) {
			cx = q.front().first;
			cy = q.front().second;
			res += 1LL * B * dist[cx][cy] + A;
			res %= mod;
			q.pop_front();
			for (int d = 1; d <= 6; d++) {
				int nx = cx + dx[d];
				int ny = cy + dy[d];
				if (0 <= nx && nx < 4069 && 0 <= ny && ny < 4069 && dist[nx][ny] == -1) {
					dist[nx][ny] = dist[cx][cy] + 1;
					q.push_back({nx, ny});
				}
			}
		}
		return res;
	}
	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);
		}
	}
	if (B == 0 && (!local || subtask == 4 || subtask == 5)) {
		long long res = 0;
		for (auto C: comps) {
			res += C.calc();
			res %= mod;
		}
		if (res < 0) {
			res += mod;
		}
		res = res * A % mod;
		return res;
	}
	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 / 3
• Subtask 2: 6 / 6
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 19 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16