Submission #1237177

#TimeUsernameProblemLanguageResultExecution timeMemory
1237177MuhammadSaramRectangles (IOI19_rect)C++20
0 / 100
72 ms147016 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; const int M = 2500*2500; int col[M], mn[M][2], mx[M][2]; vector<int> ver[M]; void add(int u,int v) { u=col[u], v=col[v]; if (u==v) return; if (ver[u].size()<ver[v].size()) swap(u,v); for (int i:ver[v]) col[i]=u, ver[u].push_back(i); for (int j=0;j<2;j++) mn[u][j]=min(mn[u][j],mn[v][j]), mx[u][j]=max(mx[u][j],mx[v][j]); ver[v].clear(); } long long count_rectangles(vector<vector<int>> a) { int n=a.size(), m=a[0].size(); for (int i=1;i+1<n;i++) for (int j=1;j+1<m;j++) if (!a[i][j]) col[i*m+j]=i*m+j, mn[i*m+j][0]=mx[i*m+j][0]=i, mn[i*m+j][1]=mx[i*m+j][1]=j, ver[i*m+j]={i*m+j}; for (int i=1;i+1<n;i++) for (int j=1;j+1<m;j++) { if (a[i][j]) continue; if (i>1 && !a[i-1][j]) add(i*m+j-m,i*m+j); if (j>1 && !a[i][j-1]) add(i*m+j-1,i*m+j); } int ans=0; for (int i=1;i<n-1;i++) for (int j=1;j<m-1;j++) if(col[i*m+j]==i*m+j) { int ar=(mx[i*m+j][0]-mn[i*m+j][0]+1)*(mx[i*m+j][1]-mn[i*m+j][1]+1); if (ar==ver[i*m+j].size()) ans++; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...