QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #163042 | #7105. Pixel Art | ucup-team228 | TL | 13ms | 112368kb | C++20 | 7.4kb | 2023-09-03 19:19:07 | 2023-09-03 19:19:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct DSU {
static const int N = 1e6 + 10;
int Parent[N], Rank[N], Size[N], cnt;
void init(int n) {
for (int i = 1; i <= n; i++) {
Parent[i] = i, Rank[i] = 0, Size[i] = 1;
}
cnt = n;
}
int find(int v) {
if (Parent[v] == v) return v;
else return Parent[v] = find(Parent[v]);
}
void unite(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (Rank[u] < Rank[v]) swap(u, v);
if (Rank[v] == Rank[u]) Rank[u]++;
Parent[v] = u, cnt--;
Size[u] += Size[v];
}
};
DSU dsu;
#define close my_close
const int N = 5e5 + 10;
int r1[N], c1[N], r2[N], c2[N];
bool dead[N];
vector<pair<int, int>> row[N], col[N];
set<pair<int, int>> col_lef[N], col_rig[N];
vector<int> open[N], close[N];
ll cnt_black[N];
void init(int n, int m, int k) {
for (int i = 0; i <= n + 1; i++) {
row[i].clear();
open[i].clear();
close[i].clear();
cnt_black[i] = 0;
}
for (int j = 0; j <= m + 1; j++) {
col[j].clear();
col_lef[j].clear();
col_rig[j].clear();
}
for (int i = 1; i <= k; i++) {
dead[i] = false;
}
}
void merge(int n, int m, int k) {
for (int i = 1; i <= k; i++) {
if (dead[i]) {
continue;
} else if (r1[i] == r2[i]) {
row[r1[i]].emplace_back(c1[i], i);
} else {
col[c1[i]].emplace_back(r1[i], i);
}
}
for (int i = 1; i <= n; i++) {
sort(row[i].begin(), row[i].end());
for (int j = int(row[i].size()) - 1; j >= 1; j--) {
int x = row[i][j - 1].second;
int y = row[i][j].second;
if (c2[x] + 1 == c1[y]) {
dead[y] = true;
c2[x] = c2[y];
}
}
}
for (int j = 1; j <= m; j++) {
sort(col[j].begin(), col[j].end());
for (int i = int(col[j].size()) - 1; i >= 1; i--) {
int x = col[j][i - 1].second;
int y = col[j][i].second;
if (r2[x] + 1 == r1[y]) {
dead[y] = true;
r2[x] = r2[y];
}
}
}
}
bool check(int i, int j) {
return max(c1[i], c1[j]) <= min(c2[i], c2[j]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int t;
cin >> t;
while (t--) {
int n, m, k;
cin >> n >> m >> k;
init(n, m, k);
for (int i = 1; i <= k; i++) {
cin >> r1[i] >> c1[i] >> r2[i] >> c2[i];
}
for (int i = 1; i <= k; i++) {
if (!dead[i] && r1[i] == r2[i]) {
col_lef[c1[i]].emplace(r1[i], i);
col_rig[c2[i]].emplace(r1[i], i);
}
}
for (int i = 1; i <= k; i++) {
if (!dead[i] && r1[i] < r2[i]) {
auto lef = col_rig[c1[i] - 1].lower_bound({r1[i], 0});
auto rig = col_lef[c1[i] + 1].lower_bound({r1[i], 0});
bool ok_lef = lef != col_rig[c1[i] - 1].end() && lef->first <= r2[i];
bool ok_rig = rig != col_lef[c1[i] + 1].end() && rig->first <= r2[i];
if (ok_lef) {
if (ok_rig) {
if (lef->first <= rig->first) {
int j = lef->second;
col_rig[c2[j]].erase({r1[j], j});
c2[j] = c1[i];
col_rig[c2[j]].emplace(r1[j], j);
k++;
dead[k] = false;
r1[k] = r1[j] + 1;
r2[k] = r2[i];
c1[k] = c1[i];
c2[k] = c2[i];
r2[i] = r1[j] - 1;
} else {
int j = rig->second;
col_lef[c1[j]].erase({r1[j], j});
c1[j] = c1[i];
col_rig[c1[j]].emplace(r1[j], j);
k++;
dead[k] = false;
r1[k] = r1[j] + 1;
r2[k] = r2[i];
c1[k] = c1[i];
c2[k] = c1[i];
r2[i] = r1[j] - 1;
}
} else {
int j = lef->second;
col_rig[c2[j]].erase({r1[j], j});
c2[j] = c1[i];
col_rig[c2[j]].emplace(r1[j], j);
k++;
dead[k] = false;
r1[k] = r1[j] + 1;
r2[k] = r2[i];
c1[k] = c1[i];
c2[k] = c2[i];
r2[i] = r1[j] - 1;
}
} else if (ok_rig) {
int j = rig->second;
col_lef[c1[j]].erase({r1[j], j});
c1[j] = c1[i];
col_rig[c1[j]].emplace(r1[j], j);
k++;
dead[k] = false;
r1[k] = r1[j] + 1;
r2[k] = r2[i];
c1[k] = c1[i];
c2[k] = c1[i];
r2[i] = r1[j] - 1;
}
if (r2[i] < r1[i]) {
dead[i] = true;
}
}
}
merge(n, m, k);
/*
for (int i = 1; i <= k; i++) {
if (!dead[i]) {
cout << r1[i] << " " << c1[i] << " " << r2[i] << " " << c2[i] << "\n";
}
}
cout << "\n";
*/
for (int i = 1; i <= k; i++) {
if (!dead[i]) {
open[r1[i]].push_back(i);
close[r2[i] + 1].push_back(i);
cnt_black[r1[i]] += 1ll * (r2[i] - r1[i] + 1) * (c2[i] - c1[i] + 1);
}
}
for (int i = 1; i <= n; i++) {
cnt_black[i] += cnt_black[i - 1];
}
set<pair<int, int>> cur;
dsu.init(k);
int not_seen = k;
for (int r = 1; r <= n; r++) {
for (int i : open[r]) {
not_seen--;
vector<int> tmp;
while (true) {
auto it = cur.lower_bound({c1[i], 0});
if (it == cur.end() || !check(i, it->second)) {
break;
} else {
int j = it->second;
dsu.unite(i, j);
tmp.push_back(j);
cur.erase({c2[j], j});
}
}
for (int j : tmp) {
cur.insert({c2[j], j});
}
}
for (int i : close[r]) {
cur.erase({c2[i], i});
}
for (int i : open[r]) {
cur.insert({c2[i], i});
}
cout << cnt_black[r] << " " << dsu.cnt - not_seen << "\n";
}
}
#ifdef LOCAL
cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 13ms
memory: 112368kb
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
Time Limit Exceeded
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 100 50 100 50 200 1 100 50 200 100 200 100 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 ...