| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 815816 | resting | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
int id(int x, int y) { return x + y * n; }
struct val {
int cnt, x1, y1, x2, y2;
bool used = 0;
val(int x, int y) : cnt(1), x1(x), x2(x), y1(y), y2(y) {};
};
val ad(val a, val b) {
a.x1 = min(a.x1, b.x1);
a.x2 = max(a.x2, b.x2);
a.y1 = min(a.y1, b.y1);
a.y2 = max(a.y2, b.y2);
a.cnt += b.cnt;
a.used = 0;
return a;
}
bool is(val a) {
return (a.x2 - a.x1 + 1) * (a.y2 - a.y1 + 1) == a.cnt && !a.used;
}
struct dsu {
vector<int> p;
vector<val> d;
dsu() {
p = vector<int>(n * m, -1);
d = vector<val>(n * m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
d[id(i, j)] = val(i, j);
}
}
}
int getp(int v) {
return p[v] == -1 ? v : p[v] = getp(p[v]);
}
void merge(int a, int b) {
a = getp(a); b = getp(b);
if (a == b) return;
if (d[a].cnt < d[b].cnt) swap(a, b);
d[a] = ad(d[a], d[b]);
p[b] = a;
}
};
bool in_bounds(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int mx = 7e6 + 5;
long long count_rectangles(std::vector<std::vector<int>> a) {
n = a.size(); m = a[0].size();
dsu ac;
vector<pair<int, int>> uwu[mx];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
uwu[a[i][j]].push_back({ i, j });
}
}
vector<vector<int>> active(n, vector<int>(m, 0));
int res = 0;
for (int i = 0; i < mx; i++) {
for (auto& t : uwu[i]) {
auto [x, y] = t;
active[x][y] = 1;
for (int j = 0; j < 4; j++) {
int x2 = x + dx[j], y2 = y + dy[j];
if (!in_bounds(x2, y2) || !active[x2][y2]) continue;
ac.merge(id(x, y), id(x2, y2));
}
}
for (auto& t : uwu[i]) {
auto [x, y] = t;
int v = ac.getp(id(x, y));
if (is(ac.d[v])) {
ac.d[v].used = 1; res++;
}
}
}
return res;
}