QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#175218 | #7105. Pixel Art | mendicillin2# | RE | 0ms | 4248kb | C++17 | 4.9kb | 2023-09-10 16:50:07 | 2023-09-10 16:50:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using ll = int64_t;
using vi = vc<int>;
using pii = pair<int, int>;
using uint = uint32_t;
using ull = uint64_t;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
template <class F>
struct ycr {
F f;
template <class T> explicit ycr(T&& f_) : f(forward<T>(f_)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) {
return f(ref(*this), forward<Args>(args)...);
}
};
template <class F> decltype(auto) yc(F&& f) {
return ycr<decay_t<F>>(forward<F>(f));
}
struct GC {
char buf[1 << 16];
size_t s = 0, e = 0;
char operator()() {
if (s >= e) {
buf[0] = 0;
s = 0;
e = fread(buf, 1, sizeof(buf), stdin);
}
return buf[s++];
}
} gc;
template <class T> T scan_int() {
char c;
while ((c = gc()) < 40);
if (c == '-') return -scan_int<T>();
T a = c - '0';
while (isdigit(c = gc())) a = a * 10 + c - '0';
return a;
}
int scan() {
return scan_int<int>();
}
const int MAXM = 1.1e5;
int idx_ver[MAXM];
void solve() {
int N = scan();
int M = scan();
int K = scan();
struct hor_t {
int l, r;
int i;
bool operator < (const hor_t& o) const {
return l < o.l;
}
};
struct ver_t {
int c;
int i;
bool operator < (const ver_t& o) const {
return c < o.c;
}
};
vector<vector<hor_t>> hors(N);
vector<vector<ver_t>> vers(N+1);
for (int k = 0; k < K; k++) {
int r1 = scan()-1;
int c1 = scan()-1;
int r2 = scan()-1;
int c2 = scan()-1;
if (r1 == r2) {
hors[r1].push_back({c1, c2, k});
} else if (c1 == c2) {
vers[r1].push_back({c1, k});
vers[r2+1].push_back({~c1, k});
} else assert(false);
}
vector<int> par(K, -1);
int num_ccs = 0;
auto getpar = yc([&](auto self, int i) -> int {
return par[i] < 0 ? i : (par[i] = self(par[i]));
});
auto merge = [&](int a, int b) -> void {
assert(0 <= a && a < K);
assert(0 <= b && b < K);
a = getpar(a), b = getpar(b);
if (a != b) {
num_ccs--;
if (par[a] < par[b]) swap(a, b);
par[a] += par[b];
par[b] = a;
}
};
ll cur_num = 0;
int num_vers = 0;
vector<ver_t> last_row_vers;
for (int row_num = 0; row_num <= N; row_num++) {
for (const auto& [c, k] : vers[row_num]) {
if (c >= 0) {
idx_ver[c] = k;
num_ccs++;
num_vers++;
} else {
idx_ver[~c] = -1;
num_vers--;
}
}
if (row_num == N) {
break;
}
num_ccs += int(hors[row_num].size());
cur_num += num_vers;
for (const auto& [l, r, i] : hors[row_num]) {
cur_num += r-l+1;
}
// v-v
for (auto [c, k] : vers[row_num]) {
if (c >= 0) {
if (c-1 >= 0 && idx_ver[c-1] != -1) {
merge(idx_ver[c-1], idx_ver[c]);
}
if (c+1 < M && idx_ver[c+1] != -1) {
merge(idx_ver[c], idx_ver[c+1]);
}
}
}
// v-(some h from the last row)
if (row_num >= 1) {
auto j = 0;
for (auto [c, k] : vers[row_num]) {
if (c >= 0) {
while (j < int(hors[row_num-1].size()) && hors[row_num-1][j].r < c) {
j++;
}
if (j < int(hors[row_num-1].size()) && hors[row_num-1][j].l <= c) {
merge(idx_ver[c], hors[row_num-1][j].i);
}
}
}
}
sort(hors[row_num].begin(), hors[row_num].end());
// h-h
for (int j = 0; j+1 < int(hors[row_num].size()); j++) {
if (hors[row_num][j].r+1 == hors[row_num][j+1].l) {
merge(hors[row_num][j].i, hors[row_num][j+1].i);
}
}
// h-(some v to the left/right)
for (const auto& [l, r, i] : hors[row_num]) {
if (l-1 >= 0 && idx_ver[l-1] != -1) {
merge(idx_ver[l-1], i);
}
if (r+1 < M && idx_ver[r+1] != -1) {
merge(i, idx_ver[r+1]);
}
}
// h-(some v from the last row)
if (row_num >= 1) {
last_row_vers.clear();
for (const auto& [c, i] : vers[row_num-1]) {
if (c < 0) {
last_row_vers.push_back({~c, i});
}
}
sort(last_row_vers.begin(), last_row_vers.end());
int st = 0;
for (const auto& [l, r, i] : hors[row_num]) {
while (st < int(last_row_vers.size()) && last_row_vers[st].c < l) {
st++;
}
for (int j = st; j < int(last_row_vers.size()); j++) {
if (last_row_vers[j].c > r) break;
merge(i, last_row_vers[j].i);
}
}
}
// h-(some h from the last row)
if (row_num >= 1) {
int st = 0;
for (const auto& [l, r, i] : hors[row_num]) {
while (st < int(hors[row_num-1].size()) && hors[row_num-1][st].r < l) {
st++;
}
for (int j = st; j < int(hors[row_num-1].size()); j++) {
if (max(l, hors[row_num-1][j].l) <= min(r, hors[row_num-1][j].r)) {
merge(i, hors[row_num-1][j].i);
} else {
break;
}
}
}
}
cout << cur_num << ' ' << num_ccs << '\n';
//cerr << cur_num << ' ' << num_ccs << endl;
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(20);
memset(idx_ver, -1, sizeof(idx_ver));
int T = scan();
while (T--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4248kb
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
Dangerous Syscalls
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 51 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 ...