#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef KAMIRULEZ
const bool local = true;
const int subtask = 6;
#else
const bool local = true;
const int subtask = 6;
#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) {
column cur = Col;
long long res = cur.calc(A, B);
for (int x = left_x + 1; x <= right_x; x++) {
column nxt = move_right_one(cur, column(x, bottom.eval_x(x), top.eval_x(x)));
res += nxt.calc(A, B);
res %= mod;
cur = nxt;
}
return make_pair(res, cur);
}
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) {
column cur = Col;
long long res = cur.calc(A, B);
for (int x = right_x - 1; x >= left_x; x--) {
column nxt = move_left_one(cur, column(x, bottom.eval_x(x), top.eval_x(x)));
res += nxt.calc(A, B);
res %= mod;
cur = nxt;
}
return make_pair(res, cur);
}
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;
int edge_cnt = 0;
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) - 1 <= min(comps[lid].top.p2.y, comps[rid].top.p1.y)) {
adj[lid].push_back(rid);
adj[rid].push_back(lid);
edge_cnt++;
}
}
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 time |
Memory |
Grader output |
| 1 |
Execution timed out |
2073 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
9 ms |
3176 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1032 KB |
Output is correct |
| 4 |
Correct |
4 ms |
596 KB |
Output is correct |
| 5 |
Runtime error |
6 ms |
3004 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2077 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2058 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
2067 ms |
212 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
