結果

問題 No.1920 Territory
コンテスト
ユーザー emthrm
提出日時 2023-07-22 13:56:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 718 ms / 5,000 ms
コード長 7,136 bytes
コンパイル時間 3,839 ms
コンパイル使用メモリ 284,424 KB
実行使用メモリ 42,340 KB
最終ジャッジ日時 2024-09-22 13:58:06
合計ジャッジ時間 18,633 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 998244353;
// constexpr int MOD = 1000000007;
constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};
constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};
constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U>
inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);
  }
} iosetup;

template <typename Abelian>
struct FenwickTree {
  explicit FenwickTree(const int n, const Abelian ID = 0)
      : n(n), ID(ID), data(n, ID) {}

  void add(int idx, const Abelian val) {
    for (; idx < n; idx |= idx + 1) {
      data[idx] += val;
    }
  }

  Abelian sum(int idx) const {
    Abelian res = ID;
    for (--idx; idx >= 0; idx = (idx & (idx + 1)) - 1) {
      res += data[idx];
    }
    return res;
  }

  Abelian sum(const int left, const int right) const {
    return left < right ? sum(right) - sum(left) : ID;
  }

  Abelian operator[](const int idx) const { return sum(idx, idx + 1); }

  int lower_bound(Abelian val) const {
    if (val <= ID) return 0;
    int res = 0, exponent = 1;
    while (exponent <= n) exponent <<= 1;
    for (int mask = exponent >> 1; mask > 0; mask >>= 1) {
      const int idx = res + mask - 1;
      if (idx < n && data[idx] < val) {
        val -= data[idx];
        res += mask;
      }
    }
    return res;
  }

 private:
  const int n;
  const Abelian ID;
  std::vector<Abelian> data;
};

struct UnionFind {
  explicit UnionFind(const int n) : data(n, -1) {}

  int root(const int ver) {
    return data[ver] < 0 ? ver : data[ver] = root(data[ver]);
  }

  bool unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return false;
    if (data[u] > data[v]) std::swap(u, v);
    data[u] += data[v];
    data[v] = u;
    return true;
  }

  bool is_same(const int u, const int v) { return root(u) == root(v); }

  int size(const int ver) { return -data[root(ver)]; }

 private:
  std::vector<int> data;
};

// https://atcoder.jp/contests/joi2014ho/tasks/joi2014ho5
int main() {
  constexpr int L = 200000;
  int n_, m_; cin >> n_ >> m_;
  const int n = n_ + m_;
  vector<int> a(n + 4), b(n + 4), c(n + 4), d(n + 4);
  REP(i, n_) {
    cin >> b[i] >> a[i] >> c[i];
    d[i] = b[i];
  }
  FOR(i, n_, n) {
    cin >> a[i] >> b[i] >> d[i];
    c[i] = a[i];
  }
  a[n] = b[n] = d[n] = 0; c[n] = L + 1;
  a[n + 1] = b[n + 1] = c[n + 1] = 0; d[n + 1] = L + 1;
  a[n + 2] = c[n + 2] = L + 1; b[n + 2] = 0; d[n + 2] = L + 1;
  a[n + 3] = 0; b[n + 3] = d[n + 3] = L + 1; c[n + 3] = L + 1;
  vector<int> xs{0, L + 1};
  xs.reserve((n + 4) * 6 + 2);
  copy(ALL(a), back_inserter(xs));
  REP(i, n + 4) {
    if (a[i] > 0) xs.emplace_back(a[i] - 1);
    if (a[i] + 1 <= L + 1) xs.emplace_back(a[i] + 1);
  }
  copy(ALL(c), back_inserter(xs));
  REP(i, n + 4) {
    if (c[i] > 0) xs.emplace_back(c[i] - 1);
    if (c[i] + 1 <= L + 1) xs.emplace_back(c[i] + 1);
  }
  sort(ALL(xs));
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  const int x_size = xs.size();
  vector<int> ys{0, L + 1};
  ys.reserve((n + 4) * 6 + 2);
  copy(ALL(b), back_inserter(ys));
  REP(i, n + 4) {
    if (b[i] > 0) ys.emplace_back(b[i] - 1);
    if (b[i] + 1 <= L + 1) ys.emplace_back(b[i] + 1);
  }
  copy(ALL(d), back_inserter(ys));
  REP(i, n + 4) {
    if (d[i] > 0) ys.emplace_back(d[i] - 1);
    if (d[i] + 1 <= L + 1) ys.emplace_back(d[i] + 1);
  }
  sort(ALL(ys));
  ys.erase(unique(ys.begin(), ys.end()), ys.end());
  const int y_size = ys.size();
  REP(i, n + 4) a[i] = distance(xs.begin(), lower_bound(ALL(xs), a[i]));
  REP(i, n + 4) b[i] = distance(ys.begin(), lower_bound(ALL(ys), b[i]));
  REP(i, n + 4) c[i] = distance(xs.begin(), lower_bound(ALL(xs), c[i]));
  REP(i, n + 4) d[i] = distance(ys.begin(), lower_bound(ALL(ys), d[i]));
  vector<vector<pair<int, int>>> par_y(x_size), ins_x(x_size), era_x(x_size);
  REP(i, n + 4) {
    if (a[i] == c[i]) {
      par_y[a[i]].emplace_back(b[i], d[i]);
    } else {
      ins_x[a[i]].emplace_back(b[i], i);
      era_x[c[i]].emplace_back(b[i], i);
    }
  }

  ll ans = -(n + 4);

  FenwickTree<int> bit(y_size);
  REP(x, x_size) {
    for (const auto& [y, _] : ins_x[x]) bit.add(y, 1);
    for (const auto& [y1, y2] : par_y[x]) {
      const int cross = bit.sum(y1, y2 + 1);
      ans += cross;
      if (cross == 0) ++ans;
    }
    for (const auto& [y, _] : era_x[x]) bit.add(y, -1);
  }

  UnionFind union_find(n + 4);
  vector<int> id_y(y_size, -1);
  set<int> t;
  map<int, int> intervals;
  const auto find = [&](const int y) {
    const auto it = intervals.lower_bound(y);
    if (it != intervals.end() && it->first == y) return it;
    if (it != intervals.begin() && prev(it)->first <= y && y <= prev(it)->second) return prev(it);
    return intervals.end();
  };
  REP(x, x_size) {
    for (const auto [y, id] : ins_x[x]) {
      if (const auto it = find(y); it != intervals.end()) {
        const auto [l, r] = *it;
        intervals.erase(it);
        const auto it_r = t.lower_bound(y);
        if (it_r != t.end() && *it_r <= r) {
          assert(intervals.emplace(*it_r, r).second);
        }
        if (it_r != t.begin() && *prev(it_r) >= l) {
          assert(intervals.emplace(l, *prev(it_r)).second);
        }
        assert(intervals.emplace(y, y).second);
      } else {
        assert(intervals.emplace(y, y).second);
      }
      id_y[y] = id;
      assert(t.emplace(y).second);
    }
    for (const auto& [y1, y2] : par_y[x]) {
      auto it = find(y1);
      if (it == intervals.end()) {
        it = intervals.lower_bound(y1);
        if (it != intervals.end() && it->first > y2) it = intervals.end();
      }
      if (it != intervals.end()) {
        vector<pair<int, int>> segs;
        for (; it != intervals.end() && it->first <= y2; it = intervals.erase(it)) {
          segs.emplace_back(*it);
        }
        FOR(i, 1, segs.size()) {
          union_find.unite(id_y[segs[i - 1].first], id_y[segs[i].first]);
        }
        assert(intervals.emplace(segs.front().first, segs.back().second).second);
      }
    }
    for (const auto& [y, _] : era_x[x]) {
      id_y[y] = -1;
      assert(t.erase(y) > 0);
      const auto it = find(y);
      assert(it != intervals.end());
      const auto [l, r] = *it;
      intervals.erase(it);
      const auto it_r = t.lower_bound(y);
      if (it_r != t.end() && *it_r <= r) {
        assert(intervals.emplace(*it_r, r).second);
      }
      if (it_r != t.begin() && *prev(it_r) >= l) {
        assert(intervals.emplace(l, *prev(it_r)).second);
      }
    }
  }
  REP(i, n + 4) {
    if (b[i] == d[i] && union_find.root(i) == i) ++ans;
  }
  cout << ans - 1 << '\n';
  return 0;
}
0