#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200 + 4;
int l[N][N][N];
int r[N][N][N];
int u[N][N][N];
int d[N][N][N];
int get_l(int k, int i, int j, int ii, int jj) {return l[k][ii+1][jj+1] - l[k][ii+1][j] - l[k][i][jj+1] + l[k][i][j];}
int get_r(int k, int i, int j, int ii, int jj) {return r[k][ii+1][jj+1] - r[k][ii+1][j] - r[k][i][jj+1] + r[k][i][j];}
int get_u(int k, int i, int j, int ii, int jj) {return u[k][ii+1][jj+1] - u[k][ii+1][j] - u[k][i][jj+1] + u[k][i][j];}
int get_d(int k, int i, int j, int ii, int jj) {return d[k][ii+1][jj+1] - d[k][ii+1][j] - d[k][i][jj+1] + d[k][i][j];}
long long count_rectangles(std::vector<std::vector<int>> a) {
int n = a.size();
int m = a[0].size();
for (int i=0; i<n; i++) for (int j=0; j<m; j++) {
for (int k=j-1; k>=0; k--) if (a[i][j]<a[i][k]) l[k+1][i+1][j+1]=1;
for (int k=j+1; k<m ; k++) if (a[i][j]<a[i][k]) r[k-1][i+1][j+1]=1;
for (int k=i-1; k>=0; k--) if (a[i][j]<a[k][j]) u[k+1][i+1][j+1]=1;
for (int k=i+1; k<n ; k++) if (a[i][j]<a[k][j]) d[k-1][i+1][j+1]=1;
}
// cout << r[1][1][1] << ' ' << r[1][1][2] << '\n';
// cout << r[1][2][1] << ' ' << r[1][2][2] << '\n';
for (int k=0; k<m; k++) for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) {
l[k][i][j] += l[k][i-1][j] + l[k][i][j-1] - l[k][i-1][j-1];
r[k][i][j] += r[k][i-1][j] + r[k][i][j-1] - r[k][i-1][j-1];
}
for (int k=0; k<n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) {
u[k][i][j] += u[k][i-1][j] + u[k][i][j-1] - u[k][i-1][j-1];
d[k][i][j] += d[k][i-1][j] + d[k][i][j-1] - d[k][i-1][j-1];
}
// cout << r[1][1][1] << ' ' << r[1][1][2] << '\n';
// cout << r[1][2][1] << ' ' << r[1][2][2] << '\n';
int ans=0;
for (int i=1; i+1<n; i++) for (int j=1; j+1<m; j++) {
for (int ii=i; ii+1<n; ii++) for (int jj=j; jj+1<m; jj++) {
int s = (ii-i+1) * (jj-j+1);
// if (i==j && j==ii && ii==jj && i==1) cout << (get_l(j,i,j,ii,jj)==s) << (get_r(jj,i,j,ii,jj)==s) << (get_u(i,i,j,ii,jj)==s) << (get_d(ii,i,j,ii,jj)==s) << '\n';
ans += get_l(j,i,j,ii,jj)==s && get_r(jj,i,j,ii,jj)==s && get_u(i,i,j,ii,jj)==s && get_d(ii,i,j,ii,jj)==s;
}
}
return ans;
}
# | 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... |