Submission #728099

#TimeUsernameProblemLanguageResultExecution timeMemory
728099SanguineChameleonHexagonal Territory (APIO21_hexagon)C++17
66 / 100
2078 ms97484 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...