QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#161772 | #7105. Pixel Art | ucup-team987# | RE | 3ms | 10280kb | C++23 | 8.6kb | 2023-09-03 02:00:46 | 2023-09-03 02:00:46 |
Judging History
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...