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"
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n, m;
struct DSU {
vector<int> p, sz;
vector<int> l, r;
vector<int> used;
int mx;
void reset(int s, int mm) {
p.assign(s + 3, -1);
sz.assign(s + 3, 0);
l.assign(s + 3, INF);
r.assign(s + 3, 0);
used.assign(s + 3, -1);
mx = mm;
}
void make_set(int x) {
p[x] = x;
sz[x] = 1;
l[x] = r[x] = x;
}
int find_set(int x) {
return p[x] == x ? x : find_set(p[x]);
}
void union_set(int x, int y) {
x = find_set(x); y = find_set(y);
if(x == y) return;
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
p[y] = x;
l[x] = min(l[x], l[y]);
r[x] = max(r[x], r[y]);
}
bool check_val(int x) {
return !(l[x] == 0 || r[x] == mx);
}
};
long long count_rectangles(std::vector<std::vector<int> > a) {
n = (int)a.size();
m = (int)a[0].size();
vector<vector<array<int, 3 > > > row(n), col(m);
REP(i, n - 1) {
if(i == 0) continue;
DSU ds;
ds.reset(m, m - 1);
vector<int> ord;
REP(j, m) ord.pb(j);
sort(all(ord), [&](int x, int y) {
return a[i][x] < a[i][y];
});
int last = -1, lind = 0;
for(int k = 0; k < ord.size(); k++) {
auto &c = ord[k];
if(a[i][c] != last) {
for(int j = lind; j < k; j++) {
if(ds.used[ds.find_set(ord[j])] == lind) {
continue;
}
ds.used[ds.find_set(ord[j])] = lind;
if(!ds.check_val(ds.find_set(ord[j]))) continue;
row[i].pb({ds.l[ds.find_set(ord[j])], ds.r[ds.find_set(ord[j])]});
}
last = a[i][c];
lind = k;
}
ds.make_set(c);
if(ds.p[c + 1] != -1) ds.union_set(c, c + 1);
if(c > 0 && ds.p[c - 1] != -1) ds.union_set(c, c - 1);
}
for(int j = lind; j < ord.size(); j++) {
if(ds.used[ds.find_set(ord[j])] == lind) {
continue;
}
ds.used[ds.find_set(ord[j])] = lind;
if(!ds.check_val(ds.find_set(ord[j]))) continue;
row[i].pb({ds.l[ds.find_set(ord[j])], ds.r[ds.find_set(ord[j])], 0});
}
}
REP(j, m - 1) {
if(j == 0) continue;
DSU ds;
ds.reset(n, n - 1);
vector<int> ord;
REP(i, n) ord.pb(i);
sort(all(ord), [&](int x, int y) {
return a[x][j] < a[y][j];
});
int last = -1, lind = 0;
for(int k = 0; k < ord.size(); k++) {
auto &c = ord[k];
if(a[c][j] != last) {
for(int i = lind; i < k; i++) {
if(ds.used[ds.find_set(ord[i])] == lind) {
continue;
}
ds.used[ds.find_set(ord[i])] = lind;
if(!ds.check_val(ds.find_set(ord[i]))) continue;
col[j].pb({ds.l[ds.find_set(ord[i])], ds.r[ds.find_set(ord[i])]});
}
last = a[c][j];
lind = k;
}
ds.make_set(c);
if(ds.p[c + 1] != -1) ds.union_set(c, c + 1);
if(c > 0 && ds.p[c - 1] != -1) ds.union_set(c, c - 1);
}
for(int i = lind; i < ord.size(); i++) {
if(ds.used[ds.find_set(ord[i])] == lind) {
continue;
}
ds.used[ds.find_set(ord[i])] = lind;
if(!ds.check_val(ds.find_set(ord[i]))) continue;
col[j].pb({ds.l[ds.find_set(ord[i])], ds.r[ds.find_set(ord[i])], 0});
}
}
// cout << "rows: \n";
// for(int i = 0; i < n; i++) {
// cout << "i:" << i << "\n";
// for(auto c : row[i]) {
// cout << c[0] << " " << c[1] << "\n";
// }
// }
map<array<int, 3>, int > mpp;
for(int i = n - 1; i >= 0; i--) {
for(auto &c : row[i]) {
mpp[{i, c[0], c[1]}] = c[2] = mpp[{i + 1, c[0], c[1]}] + 1;
}
}
mpp.clear();
for(int i = m - 1; i >= 0; i--) {
for(auto &c : col[i]) {
mpp[{i, c[0], c[1]}] = c[2] = mpp[{i + 1, c[0], c[1]}] + 1;
}
}
int ans = 0;
for(int i = 0; i < n; i++) {
for(auto &c : row[i]) {
for(auto cl : col[c[0]]) {
if(cl[0] != i) continue;
if(cl[1] - cl[0] + 1 <= c[2] && c[1] - c[0] + 1 <= cl[2]) {
ans++;
}
}
}
}
return ans;
}
// int main() {
// int n, m;
// cin >> n >> m;
// vector<vector<int> > grid(n,vector<int>(m));
// REP(i, n) REP(j, m) {
// cin >> grid[i][j];
// }
// cout << count_rectangles(grid) << "\n";
// return 0;
// }
Compilation message (stderr)
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int k = 0; k < ord.size(); k++) {
| ~~~^~~~~~~~~~~~
rect.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int j = lind; j < ord.size(); j++) {
| ~~^~~~~~~~~~~~
rect.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int k = 0; k < ord.size(); k++) {
| ~~^~~~~~~~~~~~
rect.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int i = lind; i < ord.size(); i++) {
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |