QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#166085 | #7105. Pixel Art | ucup-team045 | WA | 210ms | 22016kb | C++20 | 3.4kb | 2023-09-06 00:55:11 | 2023-09-06 00:55:12 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<array>
using namespace std;
using LL = long long;
int p[1000005];
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]);
}
bool merge(int x, int y){
x = find(x), y = find(y);
if (x == y) return false;
p[x] = y;
return true;
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
vector<int> id(1000005), c(1000005);
int T;
cin >> T;
while(T--){
int n, m, k;
cin >> n >> m >> k;
vector<vector<pair<int, int> > > pos(n + 2);
vector<vector<int> > add(n + 2), del(n + 2);
vector<LL> s(n + 2);
for(int i = 0; i < k; i++){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 == x2){
pos[x1].push_back({y1, y2});
s[x1] += y2 - y1 + 1;
s[x1 + 1] -= y2 - y1 + 1;
}
else{
add[x1].push_back(y1);
del[x2 + 1].push_back(y1);
s[x1] += 1;
s[x2 + 1] -= 1;
}
}
for(int i = 1; i <= n; i++) s[i] += s[i - 1];
for(int i = 1; i <= n; i++) s[i] += s[i - 1];
int conn = 0, idx = 0;
vector<array<int, 3> > last;
for(int i = 1; i <= n; i++){
for(auto x : add[i]){
++c[x];
if (!id[x]){
id[x] = ++idx;
conn += 1;
p[idx] = idx;
}
}
vector<pair<int, int> > last2;
for(auto x : del[i]){
last2.push_back({x, id[x]});
if (--c[x] == 0){
id[x] = 0;
}
}
for(auto x : add[i]){
if (id[x - 1]) conn -= merge(id[x], id[x - 1]);
if (id[x + 1]) conn -= merge(id[x], id[x + 1]);
}
sort(last2.begin(), last2.end());
sort(pos[i].begin(), pos[i].end());
int j = -1, k = -1;
vector<array<int, 3> > cur;
for(auto [l, r] : pos[i]){
++idx;
p[idx] = idx;
conn += 1;
if (j >= 0 && j < last.size()){
auto [L, R, id] = last[j];
if (max(L, l) <= min(R, r)){
conn -= merge(idx, id);
}
}
while(j + 1 < last.size() && last[j + 1][0] <= r){
auto [L, R, id] = last[++j];
if (max(L, l) <= min(R, r)){
conn -= merge(idx, id);
}
}
while(k + 1 < last2.size() && last2[k + 1].first <= r){
auto [x, id] = last2[++k];
if (x >= l && x <= r){
conn -= merge(idx, id);
}
}
if (id[l - 1]) conn -= merge(idx, id[l - 1]);
if (id[r + 1]) conn -= merge(idx, id[r + 1]);
cur.push_back({l, r, idx});
}
last.swap(cur);
cout << s[i] << ' ' << conn << '\n';
}
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 10824kb
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
Wrong Answer
time: 210ms
memory: 22016kb
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:
wrong answer 115th lines differ - expected: '10 10', found: '10 5'