QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#198810#7105. Pixel ArtckisekiAC ✓367ms17604kbC++203.7kb2023-10-03 17:26:182023-10-03 17:26:18

Judging History

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

  • [2023-10-03 17:26:18]
  • 评测
  • 测评结果:AC
  • 用时:367ms
  • 内存:17604kb
  • [2023-10-03 17:26:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int cnt = sizeof...(T);
  (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
  cerr << "\e[1;32m[ " << s << " ] = [ ";
  for (int f = 0; L != R; ++L)
    cerr << (f++ ? ", " : "") << *L;
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

struct Dsu {
  vector<int> pa, rk;
  Dsu(int n) : pa(n), rk(n) {
    iota(pa.begin(), pa.end(), 0);
  }
  int anc(int x) {
    return pa[x] == x ? x : pa[x]=anc(pa[x]);
  }
  bool join(int x, int y) {
    x = anc(x);
    y = anc(y);
    if (x == y) return false;
    if (rk[x] < rk[y]) swap(x, y);
    return pa[y] = x, rk[x] != rk[y] || ++rk[x];
  }
};

void solve() {
  int n, m, k;
  cin >> n >> m >> k;

  vector<vector<pair<int,int>>> in(n + 1), out(n + 1);
  vector<vector<tuple<int,int,int>>> hori(n + 1);
  vector<int64_t> hcnt(n + 1);
  for (int i = 0; i < k; i++) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a == c) {
      // horizontal
      hori[a].emplace_back(b, d, i);
      hcnt[a] += d - b + 1;
    } else {
      assert (b == d);
      hori[a].emplace_back(b, b, i);
      hori[c].emplace_back(b, b, i);

      in[a].emplace_back(b, i);
      out[c].emplace_back(b, i);
    }
  }

  for (int i = 1; i <= n; i++) {
    sort(all(hori[i]));
    sort(all(in[i]));
    sort(all(out[i]));
  }

  map<int, int> vert;

  Dsu dsu(k);
  int CC = 0;
  const auto add_edge = [&](int u, int v) {
    if (dsu.join(u, v)) --CC;
  };

  const auto add_hori_hori = [&](const auto &x, const auto &y) {
    const auto get_r = [&](const auto &z) { return get<1>(z); };
    const auto get_l = [&](const auto &z) { return get<0>(z); };
    const auto get_id = [&](const auto &z) { return get<2>(z); };
    size_t j = 0;
    for (const auto &[l, r, id]: x) {
      while (j < y.size() && get_r(y[j]) < l)
        ++j;
      while (j < y.size() && get_r(y[j]) <= r) {
        add_edge(id, get_id(y[j]));
        ++j;
      }
      if (j < y.size() && get_l(y[j]) >= l && get_l(y[j]) <= r) {
        add_edge(id, get_id(y[j]));
      }
      if (j < y.size() && get_l(y[j]) <= l && get_r(y[j]) >= r) {
        add_edge(id, get_id(y[j]));
      }
    }
  };

  int64_t black = 0;
  vector<int> vis(k);
  for (int i = 1; i <= n; i++) {
    black += hcnt[i];
    for (auto [l, r, id]: hori[i])
      if (vis[id]++ == 0)
        ++CC;

    add_hori_hori(hori[i], hori[i - 1]);

    // hori[i] with hori[i]
    for (size_t j = 1; j < hori[i].size(); j++) {
      if (get<1>(hori[i][j - 1]) + 1 == get<0>(hori[i][j])) {
        add_edge(get<2>(hori[i][j - 1]), get<2>(hori[i][j]));
      }
    }

    for (auto [y, id]: in[i])
      vert[y] = id;
    for (auto [l, r, id]: hori[i]) {
      if (auto it = vert.upper_bound(r); it != vert.end()) {
        if (r + 1 == it->first)
          add_edge(id, it->second);
      }
      if (auto it = vert.lower_bound(l); it != vert.begin()) {
        if (prev(it)->first + 1 == l)
          add_edge(id, prev(it)->second);
      }
    }
    black += vert.size();

    for (auto [y, id]: out[i])
      vert.erase(y);

    cout << black << ' ' << CC << '\n';
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--)
    solve();
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

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: 0
Accepted
time: 367ms
memory: 17604kb

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:

ok 355756 lines

Extra Test:

score: 0
Extra Test Passed