Submission #412304

#	Time	Username	Problem	Language	Result	Execution time	Memory
412304		model_code	Hexagonal Territory (APIO21_hexagon)	C++17	100 / 100	271 ms	49464 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>

using namespace std;

struct Point {
  int x, y;
  Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
  Point operator+(Point p) const { return Point(x+p.x, y+p.y); }
  Point operator-(Point p) const { return Point(x-p.x, y-p.y); }
  Point operator*(int s) const { return Point(x * s, y * s); }
  bool operator==(Point p) const { return x == p.x && y == p.y; }
  bool operator<(Point p) const { return x == p.x ? y < p.y : x < p.x; }
};

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

constexpr int mod = 1e9 + 7;
const vector<Point> pdirs = { Point(0, 1), Point(1, 1), Point(1, 0),
                              Point(0, -1), Point(-1, -1), Point(-1, 0) };

long long signed_twice_area(vector<Point> & vp) {
  long long ret = 0;
  int n = (int)vp.size() - 1;
  for (int i = 0; i < n; ++i) {
    ret += 1LL * vp[i].x * vp[i+1].y - 1LL * vp[i+1].x * vp[i].y;
  }
  return ret;
}

// assumption: vp circulating the territory in counter-clockwise direction
vector<tuple<Point, Point, int>> find_top_bottom(vector<Point> & vp) {
  vector<tuple<Point, Point, int>> result;
  int n = (int)vp.size()-1;
  for (int i = 0; i < n; ++i) {
    Point a = vp[i], b = vp[(i+1) % n];
    Point bef = vp[(i+n-1) % n], aft = vp[(i+2) % n];
    if (a.x == b.x)
      continue;
    if (a.x < b.x) { // bottom
      int dir;
      if (a.y < b.y) {
        dir = 1;
      } else {
        assert(a.y == b.y);
        dir = 2;
      }
      if (bef.x < a.x || bef.y < a.y)
        a = a + pdirs[dir];
      if (aft.x <= b.x && aft.y < b.y)
        b = b - pdirs[dir];
      if (b < a)
        continue;
      --a.y;
      --b.y;
      result.emplace_back(a, b, -1);
    } else { // top
      int dir;
      if (a.y > b.y) {
        dir = 4;
      } else {
        assert(a.y == b.y);
        dir = 5;
      }
      if (bef.x > a.x || bef.y > a.y)
        a = a + pdirs[dir];
      if (aft.x >= b.x && aft.y > b.y)
        b = b - pdirs[dir];
      if (a < b)
        continue;
      result.emplace_back(b, a, +1);
    }
  }
  return result;
}

struct Column {
  int x, bot, top;
  int minval, mbot, mtop;
  Column(int _x, int _bot, int _top,
         int _minval = -1, int _mbot = -1, int _mtop = -1)
    : x(_x), bot(_bot), top(_top), minval(_minval), mbot(_mbot), mtop(_mtop) {}
  void update(int _minval, int _mbot, int _mtop) {
    minval = _minval;
    mbot = _mbot;
    mtop = _mtop;
    if (mbot > top) {
      minval += mbot - top;
      minval %= mod;
      mbot = mtop = top;
    }
    if (mtop < bot) {
      minval += bot - mtop;
      minval %= mod;
      mbot = mtop = bot;
    }
    mtop = min(mtop, top);
    mbot = max(mbot, bot);
  }
};

constexpr long long inv2 = (mod + 1LL) / 2;
// calc: sum(a + (i-1) * b)) for i = 1..n
long long calc_1(long long a, long long b, long long n) {
  long long ret = (2LL * a + (n-1LL) * b) % mod;
  ret = ret * n % mod;
  ret = ret * inv2 % mod;
  return ret;
}

constexpr long long inv3 = ((mod % 3) == 2 ? (mod + 1LL) : (2LL * mod + 1)) / 3;
// calc: sum(i * (a + (i-1) * b)) for i = 1..n
long long calc_2(long long a, long long b, long long n) {
  long long ret = n * (n + 1LL) % mod;
  ret = ret * inv2 % mod;
  long long mul = (2LL * n + 1LL) * inv3 % mod;
  mul = (a - b + mul * b) % mod;
  ret = ret * mul % mod;
  return ret;
}

long long calc_rectangle(int width, int minval, int same, int down, int up) {
  long long ret = 0;
  long long a = 1LL * minval * same %  mod;
  if (down) {
    a = (a + calc_1(minval+1, 1, down)) % mod;
  }
  ret += calc_1(a, same + down, width);
  if (up) {
    int len = min(up, width);
    ret += calc_2(minval+1, 1, len) + calc_2(minval+1, 1, len-1);
    if (len < width) {
      ret += calc_1(1LL * (minval + len) * up % mod, up, width - len);
    }
    if (len < up) {
      ret += calc_1(1LL * (minval + len + 1) * width % mod, width, up - len);
    }
  }
  return ret % mod;
}

long long calc(int width, int minval, int same, int down, int up,
               bool del_topleft, bool del_botright) {
  long long ret = calc_rectangle(width, minval, same, down, up);
  if (width > 1) {
    int d = width - 1;
    if (del_topleft) {
      assert(up >= d);
      ret -= calc_2(minval + (up - d + 1), 1, d);
    }
    if (del_botright) {
      int len = min(down, d);
      ret -= calc_2(minval + len + down, mod-1, len);
      if (len < d) {
        ret -= calc_2(minval + len+1, 1, d - len);
        long long a = calc_1(minval + len+2, 1, down);
        ret -= calc_1(a, down, d - len);
      }
    }
  }
  ret %= mod;
  if (ret < 0)
    ret += mod;
  return ret;
}

struct Block {
  Column left, right;
  Block(Column _left, Column _right) : left(_left), right(_right) {}

  long long move_right(long long a, long long b) {
    int dx = right.x - left.x;
    long long ret = (left.top - left.bot + right.top - right.bot + 2LL);
    ret = ((ret * (dx + 1) % mod) * inv2 % mod) * a % mod;

    right.update(left.minval + dx, left.mbot, left.mtop + dx);
    int width = right.x - left.x + 1;
    int same = left.mtop - left.mbot + 1;
    int up = right.top - left.mtop;
    int down = left.mbot - left.bot;
    bool del_toplef = left.top < right.top, del_botrig = left.bot < right.bot;
    ret += b * calc(width, left.minval, same, down, up, del_toplef, del_botrig);
    return ret % mod;
  }

  long long move_left(long long a, long long b) {
    int dx = right.x - left.x;
    long long ret = (left.top - left.bot + right.top - right.bot + 2LL);
    ret = ((ret * (dx + 1) % mod) * inv2 % mod) * a % mod;

    left.update(right.minval + dx, right.mbot - dx, right.mtop);
    int width = right.x - left.x + 1;
    int same = right.mtop - right.mbot + 1;
    int down = right.top - right.mtop;
    int up = right.mbot - left.bot;
    bool del_botrig = left.top < right.top, del_toplef = left.bot < right.bot;
    ret += b * calc(width, right.minval, same, down, up, del_toplef,
                    del_botrig);
    return ret % mod;
  }
};

struct Line {
  Point pstart, pdir;
  int id;
  Point get(int x) const {
    return pstart + (pdir * (x - pstart.x));
  }
  bool operator<(const Line & rig) const {
    int x_common = max(pstart.x, rig.pstart.x);
    return get(x_common).y < rig.get(x_common).y;
  }
};

vector<Block> find_blocks(vector<Point> & vp) {
  auto y_events = find_top_bottom(vp);
  vector<int> last(y_events.size()), sign(y_events.size());
  vector<Line> lines(y_events.size());
  vector<pair<int, int>> x_events;
  for (int i = 0; i < (int)y_events.size(); ++i) {
    Point pleft, pright;
    tie(pleft, pright, sign[i]) = y_events[i];
    last[i] = pleft.x;
    lines[i] = {pleft, (pright.y > pleft.y ? Point(1, 1) : Point(1, 0)), i};
    x_events.emplace_back(pleft.x, i);
    x_events.emplace_back(pright.x+1, ~i);
  }
  sort(x_events.begin(), x_events.end());
  set<Line> st;
  vector<Block> result;
  auto check_block = [&](set<Line>::iterator nxt, int x) {
    if (nxt != st.begin() && nxt != st.end() && sign[nxt->id] > 0) {
      auto prv = prev(nxt);
      if (sign[prv->id] < 0 && min(last[prv->id], last[nxt->id]) < x) {
        assert(last[prv->id] == last[nxt->id]);
        int xleft = last[prv->id], xright = x - 1;
        result.emplace_back(
            Column(xleft, prv->get(xleft).y+1, nxt->get(xleft).y),
            Column(xright, prv->get(xright).y+1, nxt->get(xright).y));
        last[prv->id] = last[nxt->id] = x;
      }
    }
  };
  for (auto & e : x_events) {
    int id = e.second;
    if (id < 0) {
      id = ~id;
      auto it = st.upper_bound(lines[id]);
      if (it != st.end())
        check_block(it, e.first);
      assert(it != st.begin());
      --it;
      assert(it->id == id);
      check_block(it, e.first);
      st.erase(it);
    } else {
      auto nxt = st.lower_bound(lines[id]);
      check_block(nxt, e.first);
      st.insert(lines[id]);
    }
  }
  return result;
}

vector<Block> blocks;
vector<vector<pair<int, int>>> tree;

void construct_tree() {
  tree.resize(blocks.size());
  vector<tuple<int, int, int>> events;
  for (int i = 0; i < (int)blocks.size(); ++i) {
    events.emplace_back(blocks[i].left.x, blocks[i].left.bot, i);
    events.emplace_back(blocks[i].right.x+1, blocks[i].right.bot, ~i);
  }
  int idl = -1, idr = -1;
  sort(events.begin(), events.end());
  int cnt = 0;
  for (auto & e : events) {
    int id = get<2>(e);
    if (id < 0)
      idl = ~id;
    else
      idr = id;
    if (idl >= 0 && idr >= 0 && blocks[idl].right.x+1 == blocks[idr].left.x) {
      if (blocks[idl].right.bot <= blocks[idr].left.top &&
          blocks[idr].left.bot <= blocks[idl].right.top) {
        tree[idl].emplace_back(idr, 1);
        tree[idr].emplace_back(idl, -1);
        ++cnt;
      }
    }
  }
  assert(cnt + 1 == (int)blocks.size());
}

int dfs(int v, int par, long long a, long long b) {
  int ret = 0;
  for (auto & e : tree[v]) {
    int u = e.first;
    if (u == par) continue;
    if (e.second > 0) {
      blocks[u].left.update(blocks[v].right.minval+1, blocks[v].right.mbot,
                            blocks[v].right.mtop+1);
      ret = (ret + blocks[u].move_right(a, b)) % mod;
    } else {
      blocks[u].right.update(blocks[v].left.minval+1, blocks[v].left.mbot-1,
                             blocks[v].left.mtop);
      ret = (ret + blocks[u].move_left(a, b)) % mod;
    }
    ret = (ret + dfs(u, v, a, b)) % mod;
  }
  return ret;
}

int draw_territory(int N, int A, int B, vector<int> D, vector<int> L) {
  vector<Point> vp(N+1);
  for (int i = 0; i < N; ++i) {
    vp[i+1] = vp[i] + pdirs[D[i]-1] * L[i];
  }
  if (signed_twice_area(vp) < 0) {
    reverse(vp.begin(), vp.end());
  }
  blocks = find_blocks(vp);
  construct_tree();
  long long ans = 0;
  int root = -1;
  for (int i = 0; i < (int)blocks.size(); ++i) {
    if (blocks[i].left.x > 0) continue;
    if (blocks[i].right.x < 0) continue;
    int top = blocks[i].left.top, bot = blocks[i].left.bot;
    if (blocks[i].left.top < blocks[i].right.top)
      top += -blocks[i].left.x;
    if (blocks[i].left.bot < blocks[i].right.bot)
      bot += -blocks[i].left.x;
    if (bot <= 0 && 0 <= top) {
      assert(root == -1);
      root = i;
      Block left = blocks[root], right = blocks[root];
      left.right = right.left = Column(0, bot, top, 0, 0, 0);
      ans = (ans + left.move_left(A, B)) % mod;
      ans = (ans + right.move_right(A, B)) % mod;
      ans = (ans - calc_1(A, B, top+1) - calc_1(A+B, B, -bot)) % mod;
      blocks[root].left = left.left;
      blocks[root].right = right.right;
    }
  }
  assert(root != -1);
  ans = (ans + dfs(root, -1, A, B)) % mod;
  if (ans < 0)
    ans += mod;
  return ans;
}

• 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: 18 / 18
• Subtask 8: 16 / 16