#include "rect.h"
#include <stdio.h>
using namespace std;
int can1[205][205][205]={0};
int can2[205][205][205]={0};
bool have[2505][2505]={0};
int N,M;
int l,r,u,d,con;
vector< vector<int> > tt;
void F(int x,int y)
{
if(x<0||y<0||x>=N||y>=M||tt[x][y]||have[x][y]) return;
have[x][y]=1;
con++;
l=min(l,y);
r=max(r,y);
u=min(u,x);
d=max(d,x);
F(x,y+1);
F(x,y-1);
F(x+1,y);
F(x-1,y);
}
long long count_rectangles(vector< vector<int> > all)
{
int i,j,k,m,n,big=0,ok;
long long ans=0;
N=all.size();
M=all[0].size();
tt=all;
if(N==3)
{
for(i=1;i<M-1;i++)
{
ok=1;
big=0;
for(j=i;j<M-1;j++)
{
if(all[1][j]>=all[0][j]||all[1][j]>=all[2][j]) ok=0;
big=max(big,all[1][j]);
if(ok&&big<min(all[1][i-1],all[1][j+1])) ans++;
}
}
return ans;
}
else if(N<3) return 0;
else if(max(N,M)<=200)
{
for(i=1;i<N;i++)
{
for(j=1;j<M;j++)
{
big=0;
for(k=j;k<M-1;k++)
{
big=max(big,all[i][k]);
if(big<all[i][j-1]&&big<all[i][k+1]) can1[i][j][k]=1;
can1[i][j][k]+=can1[i-1][j][k];
}
}
}
for(i=1;i<M;i++)
{
for(j=1;j<N;j++)
{
big=0;
for(k=j;k<N-1;k++)
{
big=max(big,all[k][i]);
if(big<all[j-1][i]&&big<all[k+1][i]) can2[i][j][k]=1;
can2[i][j][k]+=can2[i-1][j][k];
}
}
}
for(i=1;i<N-1;i++)
{
for(j=i;j<N-1;j++)
{
for(k=1;k<M-1;k++)
{
for(l=k;l<M-1;l++)
{
if(can1[j][k][l]-can1[i-1][k][l]==j-i+1&&can2[l][i][j]-can2[k-1][i][j]==l-k+1) ans++;
}
}
}
}
//printf("%lld\n",ans);
}
else
{
ans=0;
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
con=0;
u=1e9;
d=0;
l=1e9;
r=0;
if(!have[i][j]&&all[i][j]==0)
{
F(i,j);
//printf("%d %d %d %d %d\n",l,r,u,d,con);
if((r-l+1)*(d-u+1)==con&&l!=0&&r!=M-1&&u!=0&&d!=N-1) ans++;
}
}
}
//printf("%lld\n",ans);
//while(1) ans=ans;
}
return ans;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:27:15: warning: unused variable 'm' [-Wunused-variable]
27 | int i,j,k,m,n,big=0,ok;
| ^
rect.cpp:27:17: warning: unused variable 'n' [-Wunused-variable]
27 | int i,j,k,m,n,big=0,ok;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
1792 KB |
Output is correct |
3 |
Correct |
3 ms |
1792 KB |
Output is correct |
4 |
Correct |
2 ms |
1792 KB |
Output is correct |
5 |
Correct |
2 ms |
1792 KB |
Output is correct |
6 |
Correct |
2 ms |
1792 KB |
Output is correct |
7 |
Correct |
1 ms |
1024 KB |
Output is correct |
8 |
Correct |
1 ms |
896 KB |
Output is correct |
9 |
Correct |
2 ms |
1792 KB |
Output is correct |
10 |
Correct |
2 ms |
1792 KB |
Output is correct |
11 |
Correct |
2 ms |
1920 KB |
Output is correct |
12 |
Correct |
2 ms |
1920 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
1792 KB |
Output is correct |
20 |
Correct |
1 ms |
1024 KB |
Output is correct |
21 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
1792 KB |
Output is correct |
3 |
Correct |
3 ms |
1792 KB |
Output is correct |
4 |
Correct |
2 ms |
1792 KB |
Output is correct |
5 |
Correct |
2 ms |
1792 KB |
Output is correct |
6 |
Correct |
2 ms |
1792 KB |
Output is correct |
7 |
Correct |
1 ms |
1024 KB |
Output is correct |
8 |
Correct |
1 ms |
896 KB |
Output is correct |
9 |
Correct |
2 ms |
1792 KB |
Output is correct |
10 |
Correct |
2 ms |
1792 KB |
Output is correct |
11 |
Correct |
2 ms |
1920 KB |
Output is correct |
12 |
Correct |
2 ms |
1920 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
36 ms |
10880 KB |
Output is correct |
18 |
Correct |
32 ms |
10880 KB |
Output is correct |
19 |
Correct |
32 ms |
10880 KB |
Output is correct |
20 |
Correct |
28 ms |
10880 KB |
Output is correct |
21 |
Correct |
28 ms |
10752 KB |
Output is correct |
22 |
Correct |
28 ms |
10752 KB |
Output is correct |
23 |
Correct |
29 ms |
10880 KB |
Output is correct |
24 |
Correct |
23 ms |
5632 KB |
Output is correct |
25 |
Correct |
0 ms |
256 KB |
Output is correct |
26 |
Correct |
0 ms |
256 KB |
Output is correct |
27 |
Correct |
2 ms |
1792 KB |
Output is correct |
28 |
Correct |
1 ms |
1024 KB |
Output is correct |
29 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
1792 KB |
Output is correct |
3 |
Correct |
3 ms |
1792 KB |
Output is correct |
4 |
Correct |
2 ms |
1792 KB |
Output is correct |
5 |
Correct |
2 ms |
1792 KB |
Output is correct |
6 |
Correct |
2 ms |
1792 KB |
Output is correct |
7 |
Correct |
1 ms |
1024 KB |
Output is correct |
8 |
Correct |
1 ms |
896 KB |
Output is correct |
9 |
Correct |
2 ms |
1792 KB |
Output is correct |
10 |
Correct |
2 ms |
1792 KB |
Output is correct |
11 |
Correct |
2 ms |
1920 KB |
Output is correct |
12 |
Correct |
2 ms |
1920 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
36 ms |
10880 KB |
Output is correct |
18 |
Correct |
32 ms |
10880 KB |
Output is correct |
19 |
Correct |
32 ms |
10880 KB |
Output is correct |
20 |
Correct |
28 ms |
10880 KB |
Output is correct |
21 |
Correct |
28 ms |
10752 KB |
Output is correct |
22 |
Correct |
28 ms |
10752 KB |
Output is correct |
23 |
Correct |
29 ms |
10880 KB |
Output is correct |
24 |
Correct |
23 ms |
5632 KB |
Output is correct |
25 |
Correct |
894 ms |
65528 KB |
Output is correct |
26 |
Correct |
893 ms |
65656 KB |
Output is correct |
27 |
Correct |
905 ms |
65748 KB |
Output is correct |
28 |
Correct |
884 ms |
65640 KB |
Output is correct |
29 |
Correct |
871 ms |
65656 KB |
Output is correct |
30 |
Correct |
860 ms |
65656 KB |
Output is correct |
31 |
Correct |
922 ms |
65648 KB |
Output is correct |
32 |
Correct |
867 ms |
64664 KB |
Output is correct |
33 |
Correct |
0 ms |
256 KB |
Output is correct |
34 |
Correct |
0 ms |
256 KB |
Output is correct |
35 |
Correct |
2 ms |
1792 KB |
Output is correct |
36 |
Correct |
1 ms |
1024 KB |
Output is correct |
37 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
1792 KB |
Output is correct |
3 |
Correct |
3 ms |
1792 KB |
Output is correct |
4 |
Correct |
2 ms |
1792 KB |
Output is correct |
5 |
Correct |
2 ms |
1792 KB |
Output is correct |
6 |
Correct |
2 ms |
1792 KB |
Output is correct |
7 |
Correct |
1 ms |
1024 KB |
Output is correct |
8 |
Correct |
1 ms |
896 KB |
Output is correct |
9 |
Correct |
2 ms |
1792 KB |
Output is correct |
10 |
Correct |
2 ms |
1792 KB |
Output is correct |
11 |
Correct |
2 ms |
1920 KB |
Output is correct |
12 |
Correct |
2 ms |
1920 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
36 ms |
10880 KB |
Output is correct |
18 |
Correct |
32 ms |
10880 KB |
Output is correct |
19 |
Correct |
32 ms |
10880 KB |
Output is correct |
20 |
Correct |
28 ms |
10880 KB |
Output is correct |
21 |
Correct |
28 ms |
10752 KB |
Output is correct |
22 |
Correct |
28 ms |
10752 KB |
Output is correct |
23 |
Correct |
29 ms |
10880 KB |
Output is correct |
24 |
Correct |
23 ms |
5632 KB |
Output is correct |
25 |
Correct |
894 ms |
65528 KB |
Output is correct |
26 |
Correct |
893 ms |
65656 KB |
Output is correct |
27 |
Correct |
905 ms |
65748 KB |
Output is correct |
28 |
Correct |
884 ms |
65640 KB |
Output is correct |
29 |
Correct |
871 ms |
65656 KB |
Output is correct |
30 |
Correct |
860 ms |
65656 KB |
Output is correct |
31 |
Correct |
922 ms |
65648 KB |
Output is correct |
32 |
Correct |
867 ms |
64664 KB |
Output is correct |
33 |
Incorrect |
18 ms |
6144 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
416 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
8 ms |
384 KB |
Output is correct |
6 |
Correct |
10 ms |
384 KB |
Output is correct |
7 |
Correct |
8 ms |
384 KB |
Output is correct |
8 |
Correct |
11 ms |
384 KB |
Output is correct |
9 |
Correct |
8 ms |
384 KB |
Output is correct |
10 |
Correct |
0 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
512 KB |
Output is correct |
2 |
Correct |
122 ms |
37112 KB |
Output is correct |
3 |
Correct |
271 ms |
79736 KB |
Output is correct |
4 |
Correct |
266 ms |
80376 KB |
Output is correct |
5 |
Correct |
285 ms |
80248 KB |
Output is correct |
6 |
Correct |
182 ms |
95992 KB |
Output is correct |
7 |
Correct |
338 ms |
219384 KB |
Output is correct |
8 |
Correct |
369 ms |
255096 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
2 ms |
1792 KB |
Output is correct |
12 |
Correct |
1 ms |
1024 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
1792 KB |
Output is correct |
3 |
Correct |
3 ms |
1792 KB |
Output is correct |
4 |
Correct |
2 ms |
1792 KB |
Output is correct |
5 |
Correct |
2 ms |
1792 KB |
Output is correct |
6 |
Correct |
2 ms |
1792 KB |
Output is correct |
7 |
Correct |
1 ms |
1024 KB |
Output is correct |
8 |
Correct |
1 ms |
896 KB |
Output is correct |
9 |
Correct |
2 ms |
1792 KB |
Output is correct |
10 |
Correct |
2 ms |
1792 KB |
Output is correct |
11 |
Correct |
2 ms |
1920 KB |
Output is correct |
12 |
Correct |
2 ms |
1920 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
512 KB |
Output is correct |
16 |
Correct |
0 ms |
256 KB |
Output is correct |
17 |
Correct |
36 ms |
10880 KB |
Output is correct |
18 |
Correct |
32 ms |
10880 KB |
Output is correct |
19 |
Correct |
32 ms |
10880 KB |
Output is correct |
20 |
Correct |
28 ms |
10880 KB |
Output is correct |
21 |
Correct |
28 ms |
10752 KB |
Output is correct |
22 |
Correct |
28 ms |
10752 KB |
Output is correct |
23 |
Correct |
29 ms |
10880 KB |
Output is correct |
24 |
Correct |
23 ms |
5632 KB |
Output is correct |
25 |
Correct |
894 ms |
65528 KB |
Output is correct |
26 |
Correct |
893 ms |
65656 KB |
Output is correct |
27 |
Correct |
905 ms |
65748 KB |
Output is correct |
28 |
Correct |
884 ms |
65640 KB |
Output is correct |
29 |
Correct |
871 ms |
65656 KB |
Output is correct |
30 |
Correct |
860 ms |
65656 KB |
Output is correct |
31 |
Correct |
922 ms |
65648 KB |
Output is correct |
32 |
Correct |
867 ms |
64664 KB |
Output is correct |
33 |
Incorrect |
18 ms |
6144 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |