#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
bool u[205][205][205], d[205][205][205], ud[205][205][205], l[205][205][205], r[205][205][205], lr[205][205][205];
bool uu[5][5][2505], dd[5][5][2505], uudd[5][5][2505], ll[2505][2505][5], rr[2505][2505][5], llrr[2505][2505][5];
long long count_rectangles(vector<vector<int> > a)
{
int n=a.size(), m=a[0].size();
if (n<=3)
{
for (int i=1; i<=n-2; i++)
{
for (int j=i; j<=n-2; j++)
{
for (int k=1; k<=m-2; k++)
{
if (i==j)
uu[i][j][k]=(a[j][k]<a[i-1][k]);
else
uu[i][j][k]=uu[i][j-1][k]&(a[j][k]<a[i-1][k]);
}
}
}
for (int j=1; j<=n-2; j++)
{
for (int i=j; i>=1; i--)
{
for (int k=1; k<=m-2; k++)
{
if (i==j)
dd[i][j][k]=(a[i][k]<a[j+1][k]);
else
dd[i][j][k]=dd[i+1][j][k]&(a[i][k]<a[j+1][k]);
uudd[i][j][k]=uu[i][j][k]&dd[i][j][k];
}
}
}
for (int i=1; i<=m-2; i++)
{
for (int j=i; j<=m-2; j++)
{
for (int k=1; k<=n-2; k++)
{
if (i==j)
ll[i][j][k]=(a[k][j]<a[k][i-1]);
else
ll[i][j][k]=ll[i][j-1][k]&(a[k][j]<a[k][i-1]);
}
}
}
for (int j=1; j<=m-2; j++)
{
for (int i=j; i>=1; i--)
{
for (int k=1; k<=n-2; k++)
{
if (i==j)
rr[i][j][k]=(a[k][i]<a[k][j+1]);
else
rr[i][j][k]=rr[i+1][j][k]&(a[k][i]<a[k][j+1]);
llrr[i][j][k]=ll[i][j][k]&rr[i][j][k];
}
}
}
int ans=0;
for (int i=1; i<=n-2; i++)
{
for (int j=i; j<=n-2; j++)
{
int L;
for (int k=1; k<m; k++)
{
if (!uudd[i][j][k-1] && uudd[i][j][k])
L=k;
else if (uudd[i][j][k-1] && !uudd[i][j][k])
{
int R=k-1;
for (int p=L; p<=R; p++)
{
for (int q=p; q<=R; q++)
{
bool ok=1;
for (int r=i; r<=j; r++)
{
if (!llrr[p][q][r])
{
ok=0;
break;
}
}
ans+=ok;
}
}
}
}
}
}
return ans;
}
else if (n<=200 && m<=200)
{
for (int i=1; i<=n-2; i++)
{
for (int j=i; j<=n-2; j++)
{
for (int k=1; k<=m-2; k++)
{
if (i==j)
u[i][j][k]=(a[j][k]<a[i-1][k]);
else
u[i][j][k]=u[i][j-1][k]&(a[j][k]<a[i-1][k]);
}
}
}
for (int j=1; j<=n-2; j++)
{
for (int i=j; i>=1; i--)
{
for (int k=1; k<=m-2; k++)
{
if (i==j)
d[i][j][k]=(a[i][k]<a[j+1][k]);
else
d[i][j][k]=d[i+1][j][k]&(a[i][k]<a[j+1][k]);
ud[i][j][k]=u[i][j][k]&d[i][j][k];
}
}
}
for (int i=1; i<=m-2; i++)
{
for (int j=i; j<=m-2; j++)
{
for (int k=1; k<=n-2; k++)
{
if (i==j)
l[i][j][k]=(a[k][j]<a[k][i-1]);
else
l[i][j][k]=l[i][j-1][k]&(a[k][j]<a[k][i-1]);
}
}
}
for (int j=1; j<=m-2; j++)
{
for (int i=j; i>=1; i--)
{
for (int k=1; k<=n-2; k++)
{
if (i==j)
r[i][j][k]=(a[k][i]<a[k][j+1]);
else
r[i][j][k]=r[i+1][j][k]&(a[k][i]<a[k][j+1]);
lr[i][j][k]=l[i][j][k]&r[i][j][k];
}
}
}
int ans=0;
for (int i=1; i<=n-2; i++)
{
for (int j=i; j<=n-2; j++)
{
int L;
for (int k=1; k<m; k++)
{
if (!ud[i][j][k-1] && ud[i][j][k])
L=k;
else if (ud[i][j][k-1] && !ud[i][j][k])
{
int R=k-1;
for (int p=L; p<=R; p++)
{
for (int q=p; q<=R; q++)
{
bool ok=1;
for (int r=i; r<=j; r++)
{
if (!lr[p][q][r])
{
ok=0;
break;
}
}
ans+=ok;
}
}
}
}
}
}
return ans;
}
else
{
int ans=0;
for (int i=1; i<=n-2; i++)
{
for (int j=1; j<=m-2; j++)
{
if (!a[i][j])
{
int x=i+1, y=j+1;
while (x<=n-2 && !a[x][j])
x++;
while (y<=m-2 && !a[i][y])
y++;
bool ok=1;
for (int k=i; k<x; k++)
{
for (int l=j; l<y; l++)
{
if (a[k][l])
{
ok=0;
break;
}
}
if (!ok)
break;
}
if (ok)
{
for (int k=i; k<x; k++)
{
if (a[k][j-1]!=1 || a[k][y]!=1)
{
ok=0;
break;
}
}
if (ok)
{
for (int k=j; k<y; k++)
{
if (a[i-1][k]!=1 || a[x][k]!=1)
{
ok=0;
break;
}
}
}
}
if (ok)
ans++;
for (int k=i; k<x; k++)
{
for (int l=j; l<y; l++)
{
if (a[k][l])
break;
a[k][l]=2;
}
}
}
}
}
return ans;
}
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:161:21: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
161 | int L;
| ^
rect.cpp:70:21: warning: 'L' may be used uninitialized in this function [-Wmaybe-uninitialized]
70 | int L;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1452 KB |
Output is correct |
3 |
Correct |
1 ms |
1364 KB |
Output is correct |
4 |
Correct |
1 ms |
1364 KB |
Output is correct |
5 |
Correct |
1 ms |
1364 KB |
Output is correct |
6 |
Correct |
1 ms |
1364 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
1364 KB |
Output is correct |
10 |
Correct |
1 ms |
1364 KB |
Output is correct |
11 |
Correct |
1 ms |
1364 KB |
Output is correct |
12 |
Correct |
1 ms |
1364 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
1364 KB |
Output is correct |
20 |
Correct |
1 ms |
1108 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1452 KB |
Output is correct |
3 |
Correct |
1 ms |
1364 KB |
Output is correct |
4 |
Correct |
1 ms |
1364 KB |
Output is correct |
5 |
Correct |
1 ms |
1364 KB |
Output is correct |
6 |
Correct |
1 ms |
1364 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
1364 KB |
Output is correct |
10 |
Correct |
1 ms |
1364 KB |
Output is correct |
11 |
Correct |
1 ms |
1364 KB |
Output is correct |
12 |
Correct |
1 ms |
1364 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
1364 KB |
Output is correct |
20 |
Correct |
1 ms |
1108 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
5 ms |
5844 KB |
Output is correct |
23 |
Correct |
5 ms |
5844 KB |
Output is correct |
24 |
Correct |
5 ms |
5844 KB |
Output is correct |
25 |
Correct |
4 ms |
5844 KB |
Output is correct |
26 |
Correct |
4 ms |
5852 KB |
Output is correct |
27 |
Correct |
5 ms |
5844 KB |
Output is correct |
28 |
Correct |
6 ms |
5844 KB |
Output is correct |
29 |
Correct |
3 ms |
3924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1452 KB |
Output is correct |
3 |
Correct |
1 ms |
1364 KB |
Output is correct |
4 |
Correct |
1 ms |
1364 KB |
Output is correct |
5 |
Correct |
1 ms |
1364 KB |
Output is correct |
6 |
Correct |
1 ms |
1364 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
1364 KB |
Output is correct |
10 |
Correct |
1 ms |
1364 KB |
Output is correct |
11 |
Correct |
1 ms |
1364 KB |
Output is correct |
12 |
Correct |
1 ms |
1364 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
5 ms |
5844 KB |
Output is correct |
18 |
Correct |
5 ms |
5844 KB |
Output is correct |
19 |
Correct |
5 ms |
5844 KB |
Output is correct |
20 |
Correct |
4 ms |
5844 KB |
Output is correct |
21 |
Correct |
4 ms |
5852 KB |
Output is correct |
22 |
Correct |
5 ms |
5844 KB |
Output is correct |
23 |
Correct |
6 ms |
5844 KB |
Output is correct |
24 |
Correct |
3 ms |
3924 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
1364 KB |
Output is correct |
28 |
Correct |
1 ms |
1108 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
70 ms |
29004 KB |
Output is correct |
31 |
Correct |
67 ms |
29008 KB |
Output is correct |
32 |
Correct |
49 ms |
29004 KB |
Output is correct |
33 |
Correct |
38 ms |
29036 KB |
Output is correct |
34 |
Correct |
58 ms |
29032 KB |
Output is correct |
35 |
Correct |
49 ms |
28920 KB |
Output is correct |
36 |
Correct |
48 ms |
29004 KB |
Output is correct |
37 |
Correct |
49 ms |
28536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1452 KB |
Output is correct |
3 |
Correct |
1 ms |
1364 KB |
Output is correct |
4 |
Correct |
1 ms |
1364 KB |
Output is correct |
5 |
Correct |
1 ms |
1364 KB |
Output is correct |
6 |
Correct |
1 ms |
1364 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
1364 KB |
Output is correct |
10 |
Correct |
1 ms |
1364 KB |
Output is correct |
11 |
Correct |
1 ms |
1364 KB |
Output is correct |
12 |
Correct |
1 ms |
1364 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
5 ms |
5844 KB |
Output is correct |
18 |
Correct |
5 ms |
5844 KB |
Output is correct |
19 |
Correct |
5 ms |
5844 KB |
Output is correct |
20 |
Correct |
4 ms |
5844 KB |
Output is correct |
21 |
Correct |
4 ms |
5852 KB |
Output is correct |
22 |
Correct |
5 ms |
5844 KB |
Output is correct |
23 |
Correct |
6 ms |
5844 KB |
Output is correct |
24 |
Correct |
3 ms |
3924 KB |
Output is correct |
25 |
Correct |
70 ms |
29004 KB |
Output is correct |
26 |
Correct |
67 ms |
29008 KB |
Output is correct |
27 |
Correct |
49 ms |
29004 KB |
Output is correct |
28 |
Correct |
38 ms |
29036 KB |
Output is correct |
29 |
Correct |
58 ms |
29032 KB |
Output is correct |
30 |
Correct |
49 ms |
28920 KB |
Output is correct |
31 |
Correct |
48 ms |
29004 KB |
Output is correct |
32 |
Correct |
49 ms |
28536 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
1364 KB |
Output is correct |
36 |
Correct |
1 ms |
1108 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Incorrect |
14 ms |
4176 KB |
Output isn't correct |
39 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
71504 KB |
Output is correct |
2 |
Correct |
88 ms |
57524 KB |
Output is correct |
3 |
Correct |
103 ms |
71316 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
106 ms |
71376 KB |
Output is correct |
6 |
Correct |
114 ms |
71324 KB |
Output is correct |
7 |
Correct |
116 ms |
71328 KB |
Output is correct |
8 |
Correct |
118 ms |
71312 KB |
Output is correct |
9 |
Correct |
122 ms |
71316 KB |
Output is correct |
10 |
Correct |
7 ms |
328 KB |
Output is correct |
11 |
Correct |
7 ms |
356 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
1364 KB |
Output is correct |
4 |
Correct |
1 ms |
1108 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
76 ms |
22744 KB |
Output is correct |
8 |
Correct |
155 ms |
60336 KB |
Output is correct |
9 |
Correct |
161 ms |
60652 KB |
Output is correct |
10 |
Correct |
159 ms |
61168 KB |
Output is correct |
11 |
Correct |
47 ms |
30444 KB |
Output is correct |
12 |
Correct |
93 ms |
57736 KB |
Output is correct |
13 |
Correct |
96 ms |
61068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1452 KB |
Output is correct |
3 |
Correct |
1 ms |
1364 KB |
Output is correct |
4 |
Correct |
1 ms |
1364 KB |
Output is correct |
5 |
Correct |
1 ms |
1364 KB |
Output is correct |
6 |
Correct |
1 ms |
1364 KB |
Output is correct |
7 |
Correct |
1 ms |
980 KB |
Output is correct |
8 |
Correct |
1 ms |
980 KB |
Output is correct |
9 |
Correct |
1 ms |
1364 KB |
Output is correct |
10 |
Correct |
1 ms |
1364 KB |
Output is correct |
11 |
Correct |
1 ms |
1364 KB |
Output is correct |
12 |
Correct |
1 ms |
1364 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
5 ms |
5844 KB |
Output is correct |
18 |
Correct |
5 ms |
5844 KB |
Output is correct |
19 |
Correct |
5 ms |
5844 KB |
Output is correct |
20 |
Correct |
4 ms |
5844 KB |
Output is correct |
21 |
Correct |
4 ms |
5852 KB |
Output is correct |
22 |
Correct |
5 ms |
5844 KB |
Output is correct |
23 |
Correct |
6 ms |
5844 KB |
Output is correct |
24 |
Correct |
3 ms |
3924 KB |
Output is correct |
25 |
Correct |
70 ms |
29004 KB |
Output is correct |
26 |
Correct |
67 ms |
29008 KB |
Output is correct |
27 |
Correct |
49 ms |
29004 KB |
Output is correct |
28 |
Correct |
38 ms |
29036 KB |
Output is correct |
29 |
Correct |
58 ms |
29032 KB |
Output is correct |
30 |
Correct |
49 ms |
28920 KB |
Output is correct |
31 |
Correct |
48 ms |
29004 KB |
Output is correct |
32 |
Correct |
49 ms |
28536 KB |
Output is correct |
33 |
Incorrect |
14 ms |
4176 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |