제출 #1060087

#제출 시각아이디문제언어결과실행 시간메모리
1060087UnforgettableplRectangles (IOI19_rect)C++17
50 / 100
5065 ms548176 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; long long count_rectangles01(vector<vector<int>> a){ int n = a.size(); int m = a[0].size(); long long ans = 0; vector visited = a; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(visited[i][j])continue; int minx = n; int maxx = 0; int miny = m; int maxy = 0; int area = 0; function<void(int,int)> dfs = [&](int x,int y) { if(visited[x][y])return; visited[x][y]=true; area++; minx=min(minx,x); maxx=max(maxx,x); miny=min(miny,y); maxy=max(maxy,y); if(x!=0)dfs(x-1,y); if(y!=0)dfs(x,y-1); if(x!=n-1)dfs(x+1,y); if(y!=m-1)dfs(x,y+1); }; dfs(i,j); if(minx==0)continue; if(miny==0)continue; if(maxx==n-1)continue; if(maxy==m-1)continue; if((maxx-minx+1)*(maxy-miny+1)==area)ans++; } } return ans; } long long count_rectangles(vector<vector<int>> a){ { int maxi = 0; for(auto&i:a)for(int&j:i)maxi=max(maxi,j); if(maxi<=1)return count_rectangles01(a); } int n = a.size(); int m = a[0].size(); long long ans = 0; for(int i=0;i<m;i++) { vector<int> maxi(n); vector<bool> allowedrow(n); vector allowedranges(n,vector(n,0)); for(int j=i+1;j<m-1;j++) { for(int k=0;k<n;k++) { maxi[k]=max(maxi[k],a[k][j]); allowedrow[k]=maxi[k]<a[k][i] and maxi[k]<a[k][j+1]; } const int tar = j-i; { stack<pair<int,int>> s; int last_voilater = -1; for(int k=0;k<n;k++) { if(k!=0 and !allowedrow[k-1])last_voilater=k-1; while(!s.empty() and s.top().first<a[k][j])s.pop(); if(s.empty()) { s.emplace(a[k][j],k); continue; } int l = s.top().second;l++; s.emplace(a[k][j],k); int r = s.top().second;r--; if(r<l)continue; allowedranges[l][r]++; if(l<=last_voilater)continue; if(allowedranges[l][r]==tar)ans++; } } { stack<pair<int,int>> s; int last_voilater = n; for(int k=n-1;k>=0;k--){ if(k!=n-1 and !allowedrow[k+1])last_voilater=k+1; while(!s.empty() and s.top().first<a[k][j])s.pop(); if(s.empty() or s.top().first==a[k][j]) { s.emplace(a[k][j],k); continue; } int r = s.top().second;r--; s.emplace(a[k][j],k); int l = s.top().second;l++; if(r<l)continue; allowedranges[l][r]++; if(last_voilater<=r)continue; if(allowedranges[l][r]==tar)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...