Submission #827783

#TimeUsernameProblemLanguageResultExecution timeMemory
827783BaytoroRectangles (IOI19_rect)C++17
37 / 100
5084 ms38140 KiB
#include "rect.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define pb push_back #define fr first #define sc second const int N=2505; int a[N][N],b[N],c[N],used[N][N]; int l,r,lx,rx,cnt,n,m; void dfs(int x, int y){ if(x==0 || y==0) return; if(x>n || y>m) return; if(a[x][y] || used[x][y]) return; used[x][y]=1; cnt++; l=min(l,x); r=max(r,x); lx=min(lx,y); rx=max(rx,y); dfs(x+1,y); dfs(x-1,y); dfs(x,y+1); dfs(x,y-1); } long long count_rectangles(vector<vector<int>> A) { n=A.size(); m=A[0].size(); if(min(n,m)<3) return 0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++) a[i+1][j+1]=A[i][j]; } int ans=0; if(n<=3 || (n<=2500 && m<=2500)){ for(int l=2;l<n;l++){ for(int r=l;r<n;r++){ for(int i=1;i<=m;i++){ if(l==r) b[i]=a[l][i]; else b[i]=max(b[i],a[r][i]); } for(int i=2;i<m;i++){ for(int j=i;j<m;j++){ if(b[j]>=min(a[l-1][j],a[r+1][j])) break; bool cnt=1; for(int k=l;k<=r;k++){ if(i==j) c[k]=a[k][j]; else c[k]=max(c[k],a[k][j]); if(c[k]>=min(a[k][i-1],a[k][j+1])){ cnt=0; } } ans+=cnt; } } } } } else{ for(int i=2;i<n;i++){ for(int j=2;j<m;j++){ if(used[i][j]) continue; l=1e9; r=0; lx=1e9; rx=0; cnt=0; dfs(i,j); if(l==1 || r==n) continue; if(lx==1 || rx==m) continue; if(cnt==(r-l+1)*(rx-lx+1)) 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...