QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#159317 | #7105. Pixel Art | ucup-team859# | AC ✓ | 358ms | 8844kb | C++14 | 4.6kb | 2023-09-02 17:46:38 | 2023-09-04 04:30:38 |
Judging History
answer
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
using ull = unsigned long long;
using ll = long long;
using namespace std;
struct DSU {
DSU(int n) {
par.resize(n + 1);
cntJoin = 0;
}
int root(int x) {
return par[x] == 0 ? x : par[x] = root(par[x]);
}
void join(int x, int y) {
x = root(x), y = root(y);
if (x != y) {
cntJoin++;
par[x] = y;
}
}
vector<int> par;
int cntJoin;
};
struct Line {
int r1, c1, r2, c2;
int id;
bool isV() {
return c1 == c2;
}
bool isH() {
return r1 == r2;
}
bool operator<(const Line& rhs) const {
return r1 < rhs.r1;
}
};
struct SegLine {
Line l;
SegLine(Line l) {
this->l = l;
}
bool operator<(const SegLine& rhs) const {
return l.c1 < rhs.l.c1;
}
};
int main() {
#ifdef HOME
ifstream cin("input.in");
ofstream cout("output.out");
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, m, k;
cin >> n >> m >> k;
vector<Line> lines;
for (int i = 1; i <= k; i++) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
lines.push_back({r1, c1, r2, c2, i});
}
sort(lines.begin(), lines.end());
DSU dsu(k + 1);
set<SegLine> vLines;
auto cmp = [](const SegLine& s1, const SegLine& s2) {
if (s1.l.r2 == s2.l.r2) {
return s1.l.id < s2.l.id;
}
return s1.l.r2 < s2.l.r2;
};
set<SegLine, decltype(cmp)> vLinesExp{cmp};
set<SegLine> prevLines;
long long answerSize = 0;
int pos = 0;
for (int row = 1; row <= n; row++) {
while (vLinesExp.size()) {
Line l = (*vLinesExp.begin()).l;
if (l.r2 == row - 1) {
vLines.erase(SegLine(l));
vLinesExp.erase(vLinesExp.begin());
prevLines.insert(SegLine(l));
} else {
break;
}
}
int i = pos;
while (i < k && lines[i].r1 == row) {
Line l = lines[i];
if (l.isH()) {
answerSize += l.c2 - l.c1 + 1;
}
auto itr = prevLines.upper_bound(SegLine(l));
if (itr != prevLines.begin()) {
itr = prev(itr);
}
while (itr != prevLines.end() && itr->l.c1 <= l.c2) {
if (max(itr->l.c1, l.c1) <= min(itr->l.c2, l.c2)) {
dsu.join(l.id, itr->l.id);
}
itr = next(itr);
}
i++;
}
{
i = pos;
while (i < k && lines[i].r1 == row) {
Line l = lines[i];
auto itr = vLines.upper_bound(SegLine(l));
if (itr != vLines.end() && itr->l.c1 == l.c2 + 1) {
dsu.join(l.id, itr->l.id);
}
if (itr != vLines.begin()) {
auto prv = prev(itr);
if (prv->l.c2 + 1 == l.c1) {
dsu.join(l.id, prv->l.id);
}
}
i++;
}
}
prevLines.clear();
i = pos;
while (i < k && lines[i].r1 == row) {
Line l = lines[i];
if (l.isV() && l.r1 != l.r2) {
vLines.insert(SegLine(l));
vLinesExp.insert(SegLine(l));
}
prevLines.insert(SegLine(l));
i++;
}
{
auto itr = prevLines.begin();
while (itr != prevLines.end() && next(itr) != prevLines.end()) {
auto nxt = next(itr);
Line l1 = itr->l;
Line l2 = nxt->l;
if (l1.c2 == l2.c1 - 1) {
dsu.join(l1.id, l2.id);
}
itr = nxt;
}
}
answerSize += vLines.size();
pos = i;
cout << answerSize << " " << pos - dsu.cntJoin << "\n";
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
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: 358ms
memory: 8844kb
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