제출 #622430

#제출 시각아이디문제언어결과실행 시간메모리
622430JomnoiRectangles (IOI19_rect)C++17
10 / 100
24 ms5016 KiB
#include <bits/stdc++.h> #include "rect.h" using namespace std; const int MAX_N = 2505; const int d[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; int N, M; long long ans; vector <vector <int>> A; vector <vector <bitset <705>>> validRow, validCol; vector <vector <vector <bool>>> validRow2, validCol2; int qs[MAX_N][MAX_N]; short dp[MAX_N]; bool visited[MAX_N][MAX_N]; long long count_rectangles(vector <vector <int>> a) { N = a.size(), M = a[0].size(); A.resize(N + 1, vector <int> (M + 1, 0)); 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]; } } if(N <= 700 and M <= 700) { validRow.resize(N + 1, vector <bitset <705>> (M + 1, bitset <705> (M + 1))); validCol.resize(M + 1, vector <bitset <705>> (N + 1, bitset <705> (N + 1))); for(short r = 2; r <= N - 1; r++) { for(short c1 = 2; c1 <= M - 1; c1++) { int maxA = 0; for(short c2 = c1; c2 <= M - 1; c2++) { maxA = max(maxA, A[r][c2]); if(min(A[r][c1 - 1], A[r][c2 + 1]) > maxA) { validRow[r][c1][c2] = 1; } } } } for(short c = 2; c <= M - 1; c++) { for(short r1 = 2; r1 <= N - 1; r1++) { int maxA = 0; for(short r2 = r1; r2 <= N - 1; r2++) { maxA = max(maxA, A[r2][c]); if(min(A[r1 - 1][c], A[r2 + 1][c]) > maxA) { validCol[c][r1][r2] = 1; } } } } for(short r1 = 2; r1 <= N - 1; r1++) { for(short c1 = 2; c1 <= M - 1; c1++) { for(short sz = 1; r1 + sz - 1 <= N - 1; sz++) { dp[sz] = 0; for(short c2 = c1; c2 <= M - 1; c2++) { if(validCol[c2][r1][r1 + sz - 1] == true) { dp[sz]++; } else { break; } } } for(short sz = 1; c1 + sz - 1 <= M - 1; sz++) { for(short r2 = r1; r2 <= N - 1; r2++) { if(validRow[r2][c1][c1 + sz - 1] == true) { if(dp[r2 - r1 + 1] >= sz) { ans++; } } else { break; } } } } } } else if(N == 3) { validRow2.resize(N + 1, vector <vector <bool>> (M + 1, vector <bool> (M + 1, false))); validCol2.resize(M + 1, vector <vector <bool>> (N + 1, vector <bool> (N + 1, false))); for(int r = 2; r <= N - 1; r++) { for(int c1 = 2; c1 <= M - 1; c1++) { int maxA = 0; for(int c2 = c1; c2 <= M - 1; c2++) { maxA = max(maxA, A[r][c2]); if(min(A[r][c1 - 1], A[r][c2 + 1]) > maxA) { validRow2[r][c1][c2] = true; } } } } for(int c = 2; c <= M - 1; c++) { for(int r1 = 2; r1 <= N - 1; r1++) { int maxA = 0; for(int r2 = r1; r2 <= N - 1; r2++) { maxA = max(maxA, A[r2][c]); if(min(A[r1 - 1][c], A[r2 + 1][c]) > maxA) { validCol2[c][r1][r2] = true; } } } } for(int r1 = 2; r1 <= N - 1; r1++) { for(int c1 = 2; c1 <= M - 1; c1++) { for(int sz = 1; sz <= max(N, M); sz++) { dp[sz] = 0; } for(int sz = 1; r1 + sz - 1 <= N - 1; sz++) { for(int c2 = c1; c2 <= M - 1; c2++) { if(validCol2[c2][r1][r1 + sz - 1] == true) { dp[sz]++; } else { break; } } } for(int sz = 1; c1 + sz - 1 <= M - 1; sz++) { for(int r2 = r1; r2 <= N - 1; r2++) { if(validRow2[r2][c1][c1 + sz - 1] == true) { if(dp[r2 - r1 + 1] >= sz) { ans++; } } else { break; } } } } } } else { for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { qs[i][j] = qs[i - 1][j] + qs[i][j - 1] - qs[i - 1][j - 1] + A[i][j]; } } for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { if(A[i][j] == 0 and visited[i][j] == false) { visited[i][j] = true; int minR = N, maxR = 1, minC = M, maxC = 1; queue <pair <int, int>> q; q.emplace(i, j); while(!q.empty()) { auto [ux, uy] = q.front(); q.pop(); minR = min(minR, ux); maxR = max(maxR, ux); minC = min(minC, uy); maxC = max(maxC, uy); for(int ii = 0; ii < 4; ii++) { int vx = ux + d[ii][0], vy = uy + d[ii][1]; if(vx < 1 or vx > N or vy < 1 or vy > M) { continue; } if(visited[vx][vy] == false and A[vx][vy] == 0) { visited[vx][vy] = true; q.emplace(vx, vy); } } } if(minR > 1 and minC > 1 and maxR < N and maxC < M and qs[maxR][maxC] - qs[maxR][minC - 1] - qs[minR - 1][maxC] + qs[minR - 1][minC - 1] == 0) { 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...