#include "rect.h"
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
int n,m;
vector<vector<int> > grid;
bool visited[2505][2505];
ii p[2505][2505];
int r[2505][2505];
int s[2505][2505];
int left [2505][2505];
int right[2505][2505];
int top[2505][2505];
int bottom[2505][2505];
ii parent(ii i){return (i==p[i.first][i.second])?i:p[i.first][i.second]=parent(p[i.first][i.second]);}
void unions(ii i, ii j){
i=parent(i),j=parent(j);
if (i==j) return;
if (r[i.first][i.second]<r[j.first][j.second]){
p[i.first][i.second]=j;
s[j.first][j.second]+=s[i.first][i.second];
left[j.first][j.second]=min(left[i.first][i.second],left[j.first][j.second]);
right[j.first][j.second]=max(right[i.first][i.second],right[j.first][j.second]);
top[j.first][j.second]=max(top[i.first][i.second],top[j.first][j.second]);
bottom[j.first][j.second]=min(bottom[i.first][i.second],bottom[j.first][j.second]);
}
else{
p[j.first][j.second]=i;
s[i.first][i.second]+=s[j.first][j.second];
left[i.first][i.second]=min(left[i.first][i.second],left[j.first][j.second]);
right[i.first][i.second]=max(right[i.first][i.second],right[j.first][j.second]);
top[i.first][i.second]=max(top[i.first][i.second],top[j.first][j.second]);
bottom[i.first][i.second]=min(bottom[i.first][i.second],bottom[j.first][j.second]);
if (r[i.first][i.second]==r[j.first][j.second]) r[i.first][i.second]++;
}
}
struct horST{
int st[205][9];
horST(int i){
memset(st,-1,sizeof(st));
for (int x=0;x<m;x++){
st[x][0]=grid[i][x];
}
int add=1;
int row=0;
while (st[add][row]!=-1){
for (int x=add;st[x][row]!=-1;x++){
st[x-add][row+1]=max(st[x-add][row],st[x][row]);
}
row++;
add<<=1;
}
}
int query(int i,int j){
j=j-i+1;
int row=31-__builtin_clz(j);
j-=1<<row;
return max(st[i][row],st[i+j][row]);
}
};
struct verST{
int st[205][9];
verST(int i){
memset(st,-1,sizeof(st));
for (int x=0;x<m;x++){
st[x][0]=grid[x][i];
}
int add=1;
int row=0;
while (st[add][row]!=-1){
for (int x=add;st[x][row]!=-1;x++){
st[x-add][row+1]=max(st[x-add][row],st[x][row]);
}
row++;
add<<=1;
}
}
int query(int i,int j){
j=j-i+1;
int row=31-__builtin_clz(j);
j-=1<<row;
return max(st[i][row],st[i+j][row]);
}
};
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
ii temp;
long long ans=0;
bool side[2505];
horST *horr;
long long count_rectangles(vector<vector<int> > in) {
grid=in;
n=grid.size();
m=grid[0].size();
for (int x=0;x<n;x++)
for (int y=0;y<m;y++)
if (grid[x][y]>1) goto skip1;
for (int x=0;x<n;x++){
for (int y=0;y<m;y++){
p[x][y]=ii(x,y);
r[x][y]=0;
s[x][y]=1;
left[x][y]=x;
right[x][y]=x;
top[x][y]=y;
bottom[x][y]=y;
}
}
int xx,yy;
for (int x=0;x<n;x++){
for (int y=0;y<m;y++){
if (grid[x][y]==1) continue;
for (int z=0;z<4;z++){
xx=x+dx[z];
yy=y+dy[z];
if (xx<0 || n<=xx || yy<0 || m<=yy) continue;
if (grid[xx][yy]==0) unions(ii(x,y),ii(xx,yy));
}
}
}
for (int x=1;x<n-1;x++){
for (int y=1;y<m-1;y++){
if (grid[x][y]==1) continue;
temp=parent(ii(x,y));
xx=temp.first;
yy=temp.second;
if (visited[xx][yy]) continue;
visited[xx][yy]=true;
if (left[xx][yy]==0 || right[xx][yy]==n-1 || bottom[xx][yy]==0 || top[xx][yy]==m-1) continue;
if ((right[xx][yy]-left[xx][yy]+1)*(top[xx][yy]-bottom[xx][yy]+1)==s[xx][yy]) ans++;
}
}
return ans;
skip1:
if (n==1 || n==2) return 0;
if (n>3) goto skip2;
for (int x=1;x<m-1;x++){
side[x]=(min(grid[0][x],grid[2][x])>grid[1][x]);
}
horr=new horST(2);
for (int x=1;x<m-1;x++){
if (!side[x]) continue;
for (int y=x;y<m-1;y++){
if (!side[y]) break;
if (horr->query(x,y)<min(grid[1][x-1],grid[1][y+1])) ans++;
}
}
return ans;
skip2:
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
860 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
680 KB |
Output is correct |
| 2 |
Correct |
409 ms |
133884 KB |
Output is correct |
| 3 |
Correct |
927 ms |
275012 KB |
Output is correct |
| 4 |
Correct |
865 ms |
276444 KB |
Output is correct |
| 5 |
Correct |
871 ms |
276476 KB |
Output is correct |
| 6 |
Correct |
595 ms |
133880 KB |
Output is correct |
| 7 |
Correct |
1116 ms |
265804 KB |
Output is correct |
| 8 |
Correct |
1179 ms |
271068 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 12 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 13 |
Correct |
2 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
