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;
struct dsu {
vector<int> p, s, l, r;
dsu(int n) : p(n, -1), s(n, 0), l(n), r(n) { for (int i = 0; i < n; i++) l[i] = r[i] = i; };
dsu() :dsu(0) {};
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 (s[a] < s[b]) swap(a, b);
if (s[a] == s[b]) s[a]++;
l[a] = min(l[a], l[b]);
r[a] = max(r[a], r[b]);
p[b] = a;
}
};
const int mx = 2505;
//binary index tree
struct bit {
vector<int> b; int n;
bit(int n) : n(n), b(n, 0) {}
void upd(int i, int v) { for (i++; i <= n; i += i & -i) b[i - 1] += v; }
void upd(int l, int r, int v) { upd(l, v); upd(r + 1, -v); }
int q(int i) { int v = 0; for (i++; i > 0; i -= i & -i) v += b[i - 1];return v; }
int q(int l, int r) { return q(r) - q(l - 1); }
} uwu(mx);
long long count_rectangles(vector<vector<int32_t>> a) {
int n = a.size(), m = a[0].size();
vector<vector<vector<pair<short, short>>>> vert, hori; // idfc
vert = hori = vector<vector<vector<pair<short, short>>>>(n, vector<vector<pair<short, short>>>(m));
for (int i = 0; i < n; i++) {
vector<pair<int, int>> v;
vector<int> vis(mx, 0);
for (int j = 0; j < m; j++) v.push_back(make_pair((int)a[i][j], j));
dsu ac(mx);
sort(v.begin(), v.end());
for (auto& x : v) {
auto [p, t] = x;
vis[t] = 1;
if (t && vis[t - 1]) ac.merge(t - 1, t);
if (t + 1 < m && vis[t + 1]) ac.merge(t + 1, t);
t = ac.getp(t);
if (ac.l[t] && ac.r[t] + 1 < m && a[i][ac.l[t] - 1] > p && a[i][ac.r[t] + 1] > p) {
hori[i][ac.l[t]].push_back(pair<short, short>(ac.r[t] - ac.l[t] + 1, 1));
}
}
}
for (int i = 0; i < m; i++) {
vector<pair<int, int>> v;
vector<int> vis(mx, 0);
for (int j = 0; j < n; j++) v.push_back(make_pair((int)a[j][i], j));
dsu ac(mx);
sort(v.begin(), v.end());
for (auto& x : v) {
auto [p, t] = x;
vis[t] = 1;
if (t && vis[t - 1])ac.merge(t - 1, t);
if (t + 1 < n && vis[t + 1]) ac.merge(t + 1, t);
t = ac.getp(t);
if (ac.l[t] && ac.r[t] + 1 < n && a[ac.l[t] - 1][i] > p && a[ac.r[t] + 1][i] > p) {
vert[ac.l[t]][i].push_back(pair<short, short>(ac.r[t] - ac.l[t] + 1, 1));
}
}
}
long long res = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
// cout << i << "," << j << endl;
sort(hori[i][j].begin(), hori[i][j].end());
sort(vert[i][j].begin(), vert[i][j].end());
if (i + 1 < n) {
for (auto& x : hori[i][j]) {
auto tmp = lower_bound(hori[i + 1][j].begin(), hori[i + 1][j].end(), make_pair(x.first, (short)0));
if (tmp != hori[i + 1][j].end() && tmp->first == x.first)
x.second += tmp->second;
}
}
if (j + 1 < m) {
for (auto& x : vert[i][j]) {
auto tmp = lower_bound(vert[i][j + 1].begin(), vert[i][j + 1].end(), make_pair(x.first, (short)0));
if (tmp != vert[i][j + 1].end() && tmp->first == x.first)
x.second += tmp->second;
}
}
vector<pair<int, int>> bruh;
for (auto& x : vert[i][j]) bruh.push_back(make_pair((int)x.second, (int)x.first));
sort(bruh.begin(), bruh.end());
int cur = 0;
for (auto& x : hori[i][j]) {
while (cur < bruh.size() && bruh[cur].first < x.first) {
res += uwu.q(bruh[cur].second, mx - 1);
cur++;
}
uwu.upd(x.second, 1);
}
while (cur < bruh.size()) {
res += uwu.q(bruh[cur].second, mx - 1);
cur++;
}
for (auto& x : hori[i][j]) {
uwu.upd(x.second, -1);
}
}
}
return res;
}
// int32_t main() {
// int a = count_rectangles({ {4, 8, 7, 5, 6},
// { 7, 4, 10, 3, 5 },
// { 9, 7, 20, 14, 2 },
// { 9, 14, 7, 3, 6 },
// { 5, 7, 5, 2, 7 },
// {4, 5, 13, 5, 6} });
// cout << a << endl;
// }
Compilation message (stderr)
rect.cpp: In constructor 'bit::bit(int)':
rect.cpp:27:24: warning: 'bit::n' will be initialized after [-Wreorder]
27 | vector<int> b; int n;
| ^
rect.cpp:27:17: warning: 'std::vector<int> bit::b' [-Wreorder]
27 | vector<int> b; int n;
| ^
rect.cpp:28:5: warning: when initialized here [-Wreorder]
28 | bit(int n) : n(n), b(n, 0) {}
| ^~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:102:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | while (cur < bruh.size() && bruh[cur].first < x.first) {
| ~~~~^~~~~~~~~~~~~
rect.cpp:108:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | while (cur < bruh.size()) {
| ~~~~^~~~~~~~~~~~~
# | 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... |