#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2500;
int32_t upBad[MAXN][MAXN];
int32_t downBad[MAXN][MAXN];
int32_t leftBad[MAXN][MAXN];
int32_t rightBad[MAXN][MAXN];
int32_t up[MAXN][12][MAXN], down[MAXN][12][MAXN];
int32_t Left[MAXN][12][MAXN], Right[MAXN][12][MAXN];
int n,m;
int up_query(int i, int l, int r) {
int k = 32 - __builtin_clz(r - l + 1) - 1;
return max(up[i][k][l], up[i][k][r - (1<<k) + 1]);
}
int down_query(int i, int l, int r) {
int k = 32 - __builtin_clz(r - l + 1) - 1;
return min(down[i][k][l], down[i][k][r - (1<<k) + 1]);
}
int left_query(int i, int l, int r) {
int k = 32 - __builtin_clz(r - l + 1) - 1;
return max(Left[i][k][l], Left[i][k][r - (1<<k) + 1]);
}
int right_query(int i, int l, int r) {
int k = 32 - __builtin_clz(r - l + 1) - 1;
return min(Right[i][k][l], Right[i][k][r - (1<<k) + 1]);
}
int count_rectangles(std::vector<std::vector<int32_t> > a) {
n = a.size(), m = a[0].size();
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
rightBad[i][j] = m;
downBad[i][j] = n;
upBad[i][j] = -1;
leftBad[i][j] = -1;
for(int k=j+1; k<m; k++) {
if(a[i][k] >= a[i][j]) {
rightBad[i][j] = k; break;
}
}
for(int k=j-1; k>=0; k--) {
if(a[i][k] >= a[i][j]) {
leftBad[i][j] = k; break;
}
}
for(int k=i+1; k<n; k++) {
if(a[k][j] >= a[i][j]) {
downBad[i][j] = k; break;
}
}
for(int k=i-1; k>=0; k--) {
if(a[k][j] >= a[i][j]) {
upBad[i][j] = k; break;
}
}
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
Left[j][0][i] = leftBad[i][j];
Right[j][0][i] = rightBad[i][j];
up[i][0][j] = upBad[i][j];
down[i][0][j] = downBad[i][j];
}
}
for(int k=1; k<12; k++) {
for(int i=0; i<n; i++) {
for(int j=0; j+(1<<k)-1<m; j++) {
up[i][k][j] = max(up[i][k-1][j], up[i][k-1][j+(1<<(k-1))]);
down[i][k][j] = min(down[i][k-1][j], down[i][k-1][j+(1<<(k-1))]);
}
}
for(int i=0; i<m; i++) {
for(int j=0; j+(1<<k)-1<n; j++) {
Left[i][k][j] = max(Left[i][k-1][j], Left[i][k-1][j+(1<<(k-1))]);
Right[i][k][j] = min(Right[i][k-1][j], Right[i][k-1][j+(1<<(k-1))]);
}
}
}
int ans = 0;
for(int len=1; len<=n-2; len++) {
for(int i=1; i+len-1<=n-2; i++) {
int sto[m];
for(int x=1; x+1<m; x++) {
int u, d, l, r;
bool alive;
u = i, d = i + len - 1;
// as left
l = x, r = right_query(x - 1, u, d) - 1;
sto[l] = r;
if(u <= d && l <= r) {
alive = 1;
alive &= (right_query(l - 1, u, d) > r);
alive &= (left_query(r + 1, u, d) < l);
alive &= (down_query(u - 1, l, r) > d);
alive &= (up_query(d + 1, l, r) < u);
for(int i=u; i<=d; i++) {
for(int j=l; j<=r; j++) {
alive &= (a[i][j] < a[u-1][j]);
alive &= (a[i][j] < a[d+1][j]);
alive &= (a[i][j] < a[i][l-1]);
alive &= (a[i][j] < a[i][r+1]);
}
}
ans += alive;
//if(alive) cout << "u = " << u << ", d = " << d << ", l = " << l << ", r = "<<r<<"\n";
}
// as right
l = left_query(x + 1, u, d) + 1, r = x;
if(u <= d && l <= r ) {
alive = 1;
alive &= (right_query(l - 1, u, d) > r);
alive &= (left_query(r + 1, u, d) < l);
alive &= (down_query(u - 1, l, r) > d);
alive &= (up_query(d + 1, l, r) < u);
for(int i=u; i<=d; i++) {
for(int j=l; j<=r; j++) {
alive &= (a[i][j] < a[u-1][j]);
alive &= (a[i][j] < a[d+1][j]);
alive &= (a[i][j] < a[i][l-1]);
alive &= (a[i][j] < a[i][r+1]);
}
}
ans += alive;
//if(alive) cout << "u = " << u << ", d = " << d << ", l = " << l << ", r = "<<r<<"\n";
}
}
}
}
return ans;
}
/*
g++ -std=c++17 -O2 -o rect grader.cpp rect.cpp
./rect < input.txt
*/
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:97:11: warning: variable 'sto' set but not used [-Wunused-but-set-variable]
97 | int sto[m];
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
42480 KB |
Output is correct |
2 |
Correct |
25 ms |
36184 KB |
Output is correct |
3 |
Correct |
21 ms |
42328 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
18 ms |
42400 KB |
Output is correct |
6 |
Correct |
22 ms |
42332 KB |
Output is correct |
7 |
Correct |
21 ms |
42332 KB |
Output is correct |
8 |
Correct |
25 ms |
42348 KB |
Output is correct |
9 |
Correct |
22 ms |
42328 KB |
Output is correct |
10 |
Correct |
11 ms |
21848 KB |
Output is correct |
11 |
Correct |
19 ms |
42076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |