#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int mxn=2505;
int pt,color[mxn][mxn],n,m,rw[mxn],cl[mxn],a,b;
int x[4]={0,0,1,-1};
int y[4]={1,-1,0,0};
bool check(int r1,int r2,int c1,int c2,vector<vector<int>>&arr){
for(int i=r1;i<=r2;i++){
for(int j=c1;j<=c2;j++){
if(arr[i][j]<arr[i][c1-1]&&arr[i][j]<arr[i][c2+1]&&arr[i][j]<arr[r1-1][j]&&arr[i][j]<arr[r2+1][j]){
}
else{
return false;
}
}
}
return true;
}
int funk(vector<vector<int>>&arr,int x,int y){
int n=(int)arr.size(), m=(int)arr[0].size();
if(arr[x-1][y]<=arr[x][y]||arr[x][y-1]<=arr[x][y]){
return 0;
}
int ans=0;
for(int i=x;i<n-1;i++){
for(int j=y;j<m-1;j++){
if(check(x,i,y,j,arr)){
ans++;
}
}
}
return ans;
}
void dfs(int i,int j,vector<vector<int>>&arr){
color[i][j]=1;
if(i==0||i==n-1||j==0||j==m-1){
pt=0;
}
rw[i]++,cl[j]++;
a=max(a,rw[i]),b=max(b,cl[j]);
for(int ind=0;ind<4;ind++){
i+=x[ind],j+=y[ind];
if(i>=0&&i<n&&j>=0&&j<m&&!color[i][j]&&!arr[i][j]){
dfs(i,j,arr);
}
i-=x[ind],j-=y[ind];
}
}
int task(vector<vector<int>>&arr){
n=arr.size(), m=arr[0].size();
int ans=0;
for(int i=1;i<n-1;i++){
for(int j=1;j<m-1;j++){
if(!color[i][j]&&arr[i][j]==0){
pt=1;
memset(rw,0,sizeof(rw));
memset(cl,0,sizeof(cl));
a=0,b=0;
dfs(i,j,arr);
if(pt){
for(int i=0;i<n;i++){
if(rw[i]>0&&rw[i]!=a){
pt=0;
break;
}
}
}
if(pt){
for(int i=0;i<m;i++){
if(cl[i]>0&&cl[i]!=b){
pt=0;
break;
}
}
}
ans+=pt;
}
}
}
return ans;
}
long long count_rectangles(vector<vector<int>>arr) {
int n=arr.size(), m=arr[0].size();
int ans=0;
bool q=true;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(arr[i][j]>1){
q=false;
break;
}
}
}
if(q){
return task(arr);
}
for(int i=1;i<n-1;i++){
for(int j=1;j<m-1;j++){
ans+=funk(arr,i,j);
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
300 KB |
Output is correct |
3 |
Correct |
2 ms |
300 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
460 KB |
Output is correct |
20 |
Correct |
1 ms |
424 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
300 KB |
Output is correct |
3 |
Correct |
2 ms |
300 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
460 KB |
Output is correct |
20 |
Correct |
1 ms |
424 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
65 ms |
332 KB |
Output is correct |
23 |
Correct |
65 ms |
324 KB |
Output is correct |
24 |
Correct |
65 ms |
368 KB |
Output is correct |
25 |
Correct |
17 ms |
308 KB |
Output is correct |
26 |
Correct |
42 ms |
352 KB |
Output is correct |
27 |
Correct |
37 ms |
364 KB |
Output is correct |
28 |
Correct |
28 ms |
332 KB |
Output is correct |
29 |
Correct |
7 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
300 KB |
Output is correct |
3 |
Correct |
2 ms |
300 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
65 ms |
332 KB |
Output is correct |
18 |
Correct |
65 ms |
324 KB |
Output is correct |
19 |
Correct |
65 ms |
368 KB |
Output is correct |
20 |
Correct |
17 ms |
308 KB |
Output is correct |
21 |
Correct |
42 ms |
352 KB |
Output is correct |
22 |
Correct |
37 ms |
364 KB |
Output is correct |
23 |
Correct |
28 ms |
332 KB |
Output is correct |
24 |
Correct |
7 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
0 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
460 KB |
Output is correct |
28 |
Correct |
1 ms |
424 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
2727 ms |
788 KB |
Output is correct |
31 |
Correct |
2708 ms |
788 KB |
Output is correct |
32 |
Correct |
2558 ms |
812 KB |
Output is correct |
33 |
Correct |
713 ms |
672 KB |
Output is correct |
34 |
Correct |
1247 ms |
740 KB |
Output is correct |
35 |
Correct |
1246 ms |
836 KB |
Output is correct |
36 |
Correct |
1148 ms |
812 KB |
Output is correct |
37 |
Correct |
1145 ms |
836 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
300 KB |
Output is correct |
3 |
Correct |
2 ms |
300 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
65 ms |
332 KB |
Output is correct |
18 |
Correct |
65 ms |
324 KB |
Output is correct |
19 |
Correct |
65 ms |
368 KB |
Output is correct |
20 |
Correct |
17 ms |
308 KB |
Output is correct |
21 |
Correct |
42 ms |
352 KB |
Output is correct |
22 |
Correct |
37 ms |
364 KB |
Output is correct |
23 |
Correct |
28 ms |
332 KB |
Output is correct |
24 |
Correct |
7 ms |
332 KB |
Output is correct |
25 |
Correct |
2727 ms |
788 KB |
Output is correct |
26 |
Correct |
2708 ms |
788 KB |
Output is correct |
27 |
Correct |
2558 ms |
812 KB |
Output is correct |
28 |
Correct |
713 ms |
672 KB |
Output is correct |
29 |
Correct |
1247 ms |
740 KB |
Output is correct |
30 |
Correct |
1246 ms |
836 KB |
Output is correct |
31 |
Correct |
1148 ms |
812 KB |
Output is correct |
32 |
Correct |
1145 ms |
836 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
460 KB |
Output is correct |
36 |
Correct |
1 ms |
424 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
778 ms |
4376 KB |
Output is correct |
39 |
Execution timed out |
5024 ms |
4356 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
332 KB |
Output is correct |
2 |
Correct |
16 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
972 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
13 ms |
380 KB |
Output is correct |
6 |
Correct |
11 ms |
332 KB |
Output is correct |
7 |
Correct |
11 ms |
380 KB |
Output is correct |
8 |
Correct |
11 ms |
332 KB |
Output is correct |
9 |
Correct |
10 ms |
304 KB |
Output is correct |
10 |
Correct |
1 ms |
308 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
424 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
511 ms |
35116 KB |
Output is correct |
8 |
Correct |
1425 ms |
85608 KB |
Output is correct |
9 |
Correct |
1373 ms |
86172 KB |
Output is correct |
10 |
Correct |
1402 ms |
86144 KB |
Output is correct |
11 |
Correct |
198 ms |
183560 KB |
Output is correct |
12 |
Correct |
413 ms |
441852 KB |
Output is correct |
13 |
Correct |
472 ms |
523700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
300 KB |
Output is correct |
3 |
Correct |
2 ms |
300 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
300 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
65 ms |
332 KB |
Output is correct |
18 |
Correct |
65 ms |
324 KB |
Output is correct |
19 |
Correct |
65 ms |
368 KB |
Output is correct |
20 |
Correct |
17 ms |
308 KB |
Output is correct |
21 |
Correct |
42 ms |
352 KB |
Output is correct |
22 |
Correct |
37 ms |
364 KB |
Output is correct |
23 |
Correct |
28 ms |
332 KB |
Output is correct |
24 |
Correct |
7 ms |
332 KB |
Output is correct |
25 |
Correct |
2727 ms |
788 KB |
Output is correct |
26 |
Correct |
2708 ms |
788 KB |
Output is correct |
27 |
Correct |
2558 ms |
812 KB |
Output is correct |
28 |
Correct |
713 ms |
672 KB |
Output is correct |
29 |
Correct |
1247 ms |
740 KB |
Output is correct |
30 |
Correct |
1246 ms |
836 KB |
Output is correct |
31 |
Correct |
1148 ms |
812 KB |
Output is correct |
32 |
Correct |
1145 ms |
836 KB |
Output is correct |
33 |
Correct |
778 ms |
4376 KB |
Output is correct |
34 |
Execution timed out |
5024 ms |
4356 KB |
Time limit exceeded |
35 |
Halted |
0 ms |
0 KB |
- |