QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#161772#7105. Pixel Artucup-team987#RE 3ms10280kbC++238.6kb2023-09-03 02:00:462023-09-03 02:00:46

Judging History

你现在查看的是最新测评结果

  • [2023-09-03 02:00:46]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:10280kb
  • [2023-09-03 02:00:46]
  • 提交

answer

#if __INCLUDE_LEVEL__ == 0

#include <bits/stdc++.h>

using namespace std;

#include __BASE_FILE__

namespace {

void solve() {
  int h, w, k;
  cin >> tie(h, w, k);
  vector<vector<int>> lj(h);
  vector<vector<int>> rj(h);
  static vector<vector<int>> li(1e5);
  static vector<vector<int>> ri(1e5);
  vector<int> rep_w;
  while (k--) {
    int i1, j1, i2, j2;
    cin >> tie(i1, j1, i2, j2);
    --i1, --j1, --i2, --j2;
    if (i1 == i2) {
      lj[i1].push_back(j1);
      rj[i1].push_back(j2 + 1);
    } else if (j1 == j2) {
      li[j1].push_back(i1);
      ri[j1].push_back(i2 + 1);
      rep_w.push_back(j1);
    } else {
      assert(false);
    }
  }
  ranges::sort(rep_w);
  ALL(rep_w.erase, ranges::unique(rep_w));
  for (int i : rep(h)) {
    ranges::sort(lj[i]);
    ranges::sort(rj[i]);
  }
  for (int j : rep_w) {
    ranges::sort(li[j]);
    ranges::sort(ri[j]);
  }
  auto is_black = [&](int i, int j) -> bool {
    if (i < 0 || h <= i || j < 0 || w <= j) {
      return false;
    }
    if (auto it = ranges::upper_bound(rj[i], j);
        it != rj[i].end() && lj[i][it - rj[i].begin()] <= j) {
      return true;
    }
    if (auto it = ranges::upper_bound(ri[j], i);
        it != ri[j].end() && li[j][it - ri[j].begin()] <= i) {
      return true;
    }
    return false;
  };
  vector<pair<int, int>> cells;
  auto add = [&](int i, int j) {
    if (is_black(i, j)) {
      cells.emplace_back(i, j);
    }
  };
  for (int i : rep(h)) {
    for (int t : rep(lj[i].size())) {
      add(i, lj[i][t]);
      add(i, rj[i][t] - 1);
      add(i - 1, lj[i][t]);
      add(i - 1, rj[i][t] - 1);
      add(i + 1, lj[i][t]);
      add(i + 1, rj[i][t] - 1);
      add(i, lj[i][t] - 1);
      add(i, rj[i][t]);
    }
  }
  for (int j : rep_w) {
    for (int t : rep(li[j].size())) {
      add(li[j][t], j);
      add(ri[j][t] - 1, j);
      add(li[j][t], j - 1);
      add(ri[j][t] - 1, j - 1);
      add(li[j][t], j + 1);
      add(ri[j][t] - 1, j + 1);
      add(li[j][t] - 1, j);
      add(ri[j][t], j);
    }
  }
  ranges::sort(cells);
  ALL(cells.erase, ranges::unique(cells));
  int n = cells.size();
  vector<vector<int>> g(n);
  for (int v : rep(n)) {
    auto [i, j] = cells[v];
    for (auto [ni, nj] : {pair{1, 0}, {0, 1}, {-1, 0}, {0, -1}}) {
      ni += i;
      nj += j;
      if (ranges::binary_search(cells, pair{ni, nj})) {
        int u = ranges::lower_bound(cells, pair{ni, nj}) - cells.begin();
        g[v].push_back(u);
        g[u].push_back(v);
      }
    }
  }
  vector<vector<int>> js(h);
  static vector<vector<int>> is(1e5);
  for (int v : rep(n)) {
    auto [i, j] = cells[v];
    js[i].push_back(j);
    is[j].push_back(i);
  }
  for (int i : rep(h)) {
    for (int t : rep(lj[i].size())) {
      int pj = -1;
      for (int j : ranges::subrange(ranges::lower_bound(js[i], lj[i][t]),
                                    ranges::lower_bound(js[i], rj[i][t]))) {
        if (~pj) {
          int u = ranges::lower_bound(cells, pair{i, pj}) - cells.begin();
          int v = ranges::lower_bound(cells, pair{i, j}) - cells.begin();
          g[u].push_back(v);
          g[v].push_back(u);
        }
        pj = j;
      }
    }
  }
  for (int j : rep_w) {
    for (int t : rep(li[j].size())) {
      int pi = -1;
      for (int i : ranges::subrange(ranges::lower_bound(is[j], li[j][t]),
                                    ranges::lower_bound(is[j], ri[j][t]))) {
        if (~pi) {
          int u = ranges::lower_bound(cells, pair{pi, j}) - cells.begin();
          int v = ranges::lower_bound(cells, pair{i, j}) - cells.begin();
          g[u].push_back(v);
          g[v].push_back(u);
        }
        pi = i;
      }
    }
  }
  vector<int> ans(h);
  atcoder::dsu d(n);
  int cur = 0;
  for (int v : rep(n)) {
    ++cur;
    for (int u : g[v]) {
      if (u < v) {
        if (!d.same(u, v)) {
          d.merge(u, v);
          --cur;
        }
      }
    }
    ans[cells[v].first] = cur;
  }
  vector<int64_t> c(h + 1);
  for (int j : rep_w) {
    for (int t : rep(li[j].size())) {
      ++c[li[j][t]];
      --c[ri[j][t]];
    }
  }
  for (int i : rep(h)) {
    c[i + 1] += c[i];
  }
  for (int i : rep(h)) {
    for (int t : rep(lj[i].size())) {
      c[i] += rj[i][t] - lj[i][t];
    }
  }
  for (int i : rep(h)) {
    c[i + 1] += c[i];
  }
  for (int i : rep(h)) {
    print(c[i], ans[i]);
  }
  for (int j : rep_w) {
    li[j].clear();
    ri[j].clear();
    is[j].clear();
  }
}

}  // namespace

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;
  while (t--) {
    solve();
  }
}

#else  // __INCLUDE_LEVEL__

#undef assert
#define assert(expr) (expr) || (__builtin_unreachable(), 0)

#define ALL(f, r, ...) \
  [&](auto&& _) { return f(begin(_), end(_), ##__VA_ARGS__); }(r)

namespace atcoder {

// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
 public:
  dsu() : _n(0) {}
  explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}

  int merge(int a, int b) {
    assert(0 <= a && a < _n);
    assert(0 <= b && b < _n);
    int x = leader(a), y = leader(b);
    if (x == y) return x;
    if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
    parent_or_size[x] += parent_or_size[y];
    parent_or_size[y] = x;
    return x;
  }

  bool same(int a, int b) {
    assert(0 <= a && a < _n);
    assert(0 <= b && b < _n);
    return leader(a) == leader(b);
  }

  int leader(int a) {
    assert(0 <= a && a < _n);
    if (parent_or_size[a] < 0) return a;
    return parent_or_size[a] = leader(parent_or_size[a]);
  }

  int size(int a) {
    assert(0 <= a && a < _n);
    return -parent_or_size[leader(a)];
  }

  std::vector<std::vector<int>> groups() {
    std::vector<int> leader_buf(_n), group_size(_n);
    for (int i = 0; i < _n; i++) {
      leader_buf[i] = leader(i);
      group_size[leader_buf[i]]++;
    }
    std::vector<std::vector<int>> result(_n);
    for (int i = 0; i < _n; i++) {
      result[i].reserve(group_size[i]);
    }
    for (int i = 0; i < _n; i++) {
      result[leader_buf[i]].push_back(i);
    }
    result.erase(
        std::remove_if(result.begin(), result.end(),
                       [&](const std::vector<int>& v) { return v.empty(); }),
        result.end());
    return result;
  }

 private:
  int _n;
  // root node: -1 * component size
  // otherwise: parent
  std::vector<int> parent_or_size;
};

}  // namespace atcoder

template <class T, class U = T>
bool chmin(T& x, U&& y) {
  return y < x && (x = forward<U>(y), true);
}

template <class T, class U = T>
bool chmax(T& x, U&& y) {
  return x < y && (x = forward<U>(y), true);
}

namespace std {

template <class T1, class T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
  return is >> p.first >> p.second;
}

template <class... Ts>
istream& operator>>(istream& is, tuple<Ts...>& t) {
  return apply([&is](auto&... xs) -> istream& { return (is >> ... >> xs); }, t);
}

template <class... Ts>
istream& operator>>(istream& is, tuple<Ts&...>&& t) {
  return is >> t;
}

template <class R, enable_if_t<!is_convertible_v<R, string>>* = nullptr>
auto operator>>(istream& is, R&& r) -> decltype(is >> *begin(r)) {
  for (auto&& e : r) {
    is >> e;
  }
  return is;
}

template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << p.first << ' ' << p.second;
}

template <class... Ts>
ostream& operator<<(ostream& os, const tuple<Ts...>& t) {
  auto f = [&os](const auto&... xs) -> ostream& {
    [[maybe_unused]] auto sep = "";
    ((os << exchange(sep, " ") << xs), ...);
    return os;
  };
  return apply(f, t);
}

template <class R, enable_if_t<!is_convertible_v<R, string_view>>* = nullptr>
auto operator<<(ostream& os, R&& r) -> decltype(os << *begin(r)) {
  auto sep = "";
  for (auto&& e : r) {
    os << exchange(sep, " ") << e;
  }
  return os;
}

}  // namespace std

template <class... Ts>
void print(Ts&&... xs) {
  cout << tie(xs...) << '\n';
}

inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }

#endif  // __INCLUDE_LEVEL__

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 10280kb

input:

3
2 5 2
1 1 1 2
2 3 2 5
2 5 2
1 1 1 3
2 3 2 5
3 3 3
1 1 1 2
3 1 3 2
1 3 2 3

output:

2 1
5 2
3 1
6 1
3 1
4 1
6 2

result:

ok 7 lines

Test #2:

score: -100
Runtime Error

input:

2130
2 5 2
1 1 1 2
2 3 2 5
2 5 2
1 1 1 3
2 3 2 5
3 3 3
1 1 1 2
3 1 3 2
1 3 2 3
3 100 51
1 2 2 2
1 4 2 4
1 6 2 6
1 8 2 8
1 10 2 10
1 12 2 12
1 14 2 14
1 16 2 16
1 18 2 18
1 20 2 20
1 22 2 22
1 24 2 24
1 26 2 26
1 28 2 28
1 30 2 30
1 32 2 32
1 34 2 34
1 36 2 36
1 38 2 38
1 40 2 40
1 42 2 42
1 44 2 44
...

output:

2 1
5 2
3 1
6 1
3 1
4 1
6 2
50 50
100 50
200 1
50 50
150 1
200 1
2 1
4 1
6 1
8 1
10 1
12 1
14 1
16 1
18 1
20 1
22 1
24 1
26 1
28 1
30 1
32 1
34 1
36 1
38 1
40 1
42 1
44 1
46 1
48 1
50 1
52 1
54 1
56 1
58 1
60 1
62 1
64 1
66 1
68 1
70 1
72 1
74 1
76 1
78 1
80 1
82 1
84 1
86 1
88 1
90 1
92 1
94 1
96 1...

result: