QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#159328 | #7105. Pixel Art | ucup-team866# | AC ✓ | 198ms | 19956kb | C++14 | 2.3kb | 2023-09-02 17:47:18 | 2023-09-02 17:47:18 |
Judging History
你现在查看的是测评时间为 2023-09-02 17:47:18 的历史记录
- [2023-09-04 04:30:22]
- hack成功,自动添加数据
- (//qoj.ac/hack/364)
- [2023-09-02 17:47:18]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int T, n, m, K, ans, r1[N], c1[N], r2[N], c2[N], fa[N], now[N];
ll s[N]; vector <int> r[N], in[N], out[N];
int find(int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); }
void merge(int u, int v) {
if ((u = find(u)) ^ (v = find(v)))
fa[v] = u, ans --;
}
int main() {
cin >> T;
while (T --) {
scanf ("%d%d%d", &n, &m, &K), ans = 0;
for (int i=0; i<=n; i++)
s[i] = 0, r[i]. clear(), in[i]. clear(), out[i]. clear();
for (int i=1; i<=K; i++) {
scanf ("%d%d%d%d", &r1[i], &c1[i], &r2[i], &c2[i]), fa[i] = i;
if (r1[i] == r2[i]) s[r1[i]] += c2[i] - c1[i] + 1, s[r1[i]+1] -= c2[i] - c1[i] + 1, r[r1[i]]. push_back(i);
else s[r1[i]] ++, s[r2[i]+1] --, in[r1[i]-1]. push_back(i), out[r2[i]]. push_back(i);
}
for (int i=1; i<=n; i++) s[i] += s[i-1];
for (int i=1; i<=n; i++) {
printf ("%lld ", s[i] += s[i-1]);
ans += r[i]. size() + in[i-1]. size();
sort (r[i]. begin(), r[i]. end(), [] (const int &i, const int &j) { return c1[i] < c1[j]; });
if (r[i-1]. size()) {
int j = 0, _ = r[i-1]. size();
for (int k : r[i]) {
while (j < _ && c2[r[i-1][j]] < c1[k]) j ++;
while (j < _ && c2[k] >= c1[r[i-1][j]]) merge(r[i-1][j++], k);
if (j) j --;
}
for (int k : in[i-1]) {
auto t = lower_bound (r[i-1]. begin(), r[i-1]. end(), c1[k], [] (const int &i, const int &j) { return c2[i] < j; });
if (t != r[i-1]. end() && c1[*t] <= c1[k]) merge(* t, k);
}
}
if (r[i]. size()) {
int l = 0;
for (int k : r[i]) {
if (l && c1[k] - 1 == c2[l]) merge(l, k);
l = k;
}
for (int k : out[i-1]) {
auto t = lower_bound (r[i]. begin(), r[i]. end(), c1[k], [] (const int &i, const int &j) { return c2[i] < j; });
if (t != r[i]. end() && c1[*t] <= c1[k]) merge(* t, k);
}
}
for (int k : in[i-1]) if (now[c1[k]]) merge(now[c1[k]], k);
for (int k : out[i-1]) now[c1[k]] = 0;
for (int k : in[i-1]) now[c1[k]] = k;
for (int k : in[i-1]) {
if (now[c1[k]-1]) merge(now[c1[k]-1], k);
if (now[c2[k]+1]) merge(now[c2[k]+1], k);
}
for (int k : r[i]) {
if (now[c1[k]-1]) merge(now[c1[k]-1], k);
if (now[c2[k]+1]) merge(now[c2[k]+1], k);
}
printf ("%d\n", ans);
}
for (int k : out[n]) now[c1[k]] = 0;
}
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 13884kb
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: 198ms
memory: 19956kb
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