verify/ds/area_of_union_of_rectangles.test.cpp

• View this file on GitHub
• Last update: 2024-07-04 16:49:19+08:00
• Problem: https://judge.yosupo.jp/problem/area_of_union_of_rectangles

Depends on

• lib/ds/lazysegtree.hpp
• Internal Definition (lib/internal.hpp)
• Bit Manipulation (lib/misc/bitop.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/area_of_union_of_rectangles"

#include "lib/ds/lazysegtree.hpp"

#include <limits>

constexpr int INF = std::numeric_limits<int>::max() / 2;

struct MinCnt
{
  using MS = MinCnt;
  struct S
  {
    int min, cnt;
    S() : min(INF), cnt(0) {}
    S(int min, int cnt) : min(min), cnt(cnt) {}
  };

  static S op(S x, S y)
  {
    if (x.min > y.min) return y;
    else if (x.min < y.min) return x;
    return {x.min, x.cnt + y.cnt};
  }
  static S un() { return S{}; }

  static constexpr bool cm = true;
};

struct Add
{
  using MS = Add;
  using S = int;

  static S op(S x, S y) { return x + y; }
  static S un() { return 0; }
};

struct Monoid
{
  using MS = MinCnt;
  using MA = Add;
  using S = MS::S;
  using A = MA::S;
  static S act(A a, S s, u32)
  {
    return {s.min + a, s.cnt};
  }
};

struct sweepline_t
{
  int x, l, r, v;
  sweepline_t(int x, int l, int r, int v) :
    x(x), l(l), r(r), v(v) {}
  bool operator<(const sweepline_t &sl) const
  {
    return x < sl.x;
  }
};

int main()
{
  int N;
  std::cin >> N;

  std::vector<sweepline_t> sweeplines;
  std::vector<int> cc;

  for (int i = 0; i < N; i++) {
    int x1, y1, x2, y2;
    std::cin >> x1 >> y1 >> x2 >> y2;
    cc.emplace_back(y1);
    cc.emplace_back(y2);
    sweeplines.emplace_back(x1, y1, y2, 1);
    sweeplines.emplace_back(x2, y1, y2, -1);
  }

  std::sort(cc.begin(), cc.end());
  cc.erase(std::unique(cc.begin(), cc.end()), cc.end());
  auto val = [&](int x)
  {
    return std::lower_bound(cc.begin(), cc.end(), x) - cc.begin();
  };

  std::sort(sweeplines.begin(), sweeplines.end());

  LazySegtree<Monoid> s(cc.size() - 1,
                        [&](u32 x)
                        {
                          return MinCnt::S(0, cc[x + 1] - cc[x]);
                        });

  int tot = cc.back() - cc[0];

  int m = sweeplines.size();
  i64 ans = 0;
  for (int i = 0; i + 1 < m; i++) {
    const auto &si = sweeplines[i];
    s.apply(val(si.l), val(si.r), si.v);
    int x = sweeplines[i + 1].x - si.x;
    if (x) {
      auto all = s.prod_all();
      if (all.min == 0) ans += (i64)x * (tot - all.cnt);
      else ans += (i64)x * tot;
    }
  }

  std::cout << ans << std::endl;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/home/runner/.local/lib/python3.10/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: lib/internal.hpp: line 4: #pragma once found in a non-first line

Back to top page