#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(1, i)));
events.push_back(make_pair(lines[i].p2.x, make_pair(2, 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 == 2) {
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 == 1) {
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
300 KB |
Output is correct |
| 4 |
Correct |
0 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 |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
300 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2069 ms |
296 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
2336 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Runtime error |
5 ms |
2336 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2056 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| 3 |
Correct |
1 ms |
288 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Execution timed out |
2079 ms |
212 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2047 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
