제출 #827857

#제출 시각아이디문제언어결과실행 시간메모리
827857OrazBRectangles (IOI19_rect)C++14
38 / 100
5077 ms131416 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define ll long long int #define pii pair <int, int> #define pb push_back #define ff first #define ss second const int N = 205; int mxc[N][N][N]; int mxr[N][N][N]; int row[N][N][N], col[N][N][N]; ll count_rectangles(vector<vector<int>> a){ int ans = 0, sub6 = 0; int n = a.size(), m = a[0].size(); for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++) sub6 |= (a[i][j]>1); } if (n < 3) return 0; if (n == 3){ vector<vector<vector<int>>> mx(n, vector<vector<int>>(m, vector<int>(m,0))); vector<int> P(m, 0); for (int i = 0; i < n; i++){ for (int x = 0; x < m; x++){ for (int j = 0; j < m-x; j++){ if (!x) mx[i][j][j] = a[i][j]; else mx[i][j][j+x] = max(mx[i][j][j+x-1], a[i][j+x]); } } } for (int i = 0; i < m; i++){ if (a[0][i] <= a[1][i] or a[2][i] <= a[1][i]) P[i] = 1; if (i) P[i] += P[i-1]; } int ans = 0; for (int i = 0; i < m; i++){ for (int j = i+2; j < m; j++){ if (a[1][i] > mx[1][i+1][j-1] and a[1][j] > mx[1][i+1][j-1] and !(P[j-1]-P[i])) ans++; } } return ans; } if (!sub6){ vector<vector<int>> rw(m, vector<int>(n,0)); vector<vector<int>> c(n, vector<int>(m,0)); vector<vector<int>> mat(n, vector<int>(m,0)); for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ mat[i][j] = a[i][j]; if (j) mat[i][j] += mat[i][j-1]; } } for (int i = 1; i < n; i++){ for (int j = 0; j < m; j++){ mat[i][j] += mat[i-1][j]; } } for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ c[i][j] = a[i][j]; if (j) c[i][j] += c[i][j-1]; } } for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ rw[i][j] = a[j][i]; if (j) rw[i][j] += rw[i][j-1]; } } for (int i = 1; i < n; i++){ for (int j = 0; j < m; j++){ if (a[i][j+1] == 1 or a[i][j] == 0) continue; int l = j+2, r = m-1, pos = -1; while(l <= r){ int md = (l+r)>>1; if (c[i][md]-c[i][j] > 1) r = md - 1; else if (c[i][md]-c[i][j] == 1){pos=md;r=md-1;} else l = md + 1; } if (pos == -1) continue; if (c[i-1][pos-1]-c[i-1][j] != pos-j-1) continue; l = i+1, r = n-1; int pos1 = -1; while(l <= r){ int md = (l+r)>>1; if (rw[j+1][md]-rw[j+1][i] > 1) r = md - 1; else if (rw[j+1][md]-rw[j+1][i] == 1){pos1=md;r=md-1;} else l = md + 1; } if (pos1 == -1) continue; if (c[pos1][pos-1]-c[pos1][j] != pos-j-1) continue; pos1--; if (rw[j][pos1]-rw[j][i] != pos1-i or rw[pos][pos1]-rw[pos][i] != pos1-i) continue; if (mat[pos1][pos-1]-mat[pos1][j]-mat[i-1][pos-1]+mat[i-1][j]) continue; ans++; } } return ans; } for (int i = 0; i < n; i++){ for (int x = 0; x < m; x++){ for (int j = 0; j < m-x; j++){ if (!x) mxc[i][j][j] = a[i][j]; else mxc[i][j][j+x] = max(mxc[i][j][j+x-1], a[i][j+x]); } } } for (int i = 0; i < m; i++){ for (int x = 0; x < n; x++){ for (int j = 0; j < n-x; j++){ if (!x) mxr[i][j][j] = a[j][i]; else mxr[i][j][j+x] = max(mxr[i][j][j+x-1], a[j+x][i]); } } } for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ for (int k = j+2; k < m; k++){ row[i][j][k] = (a[i][j] > mxc[i][j+1][k-1] and a[i][k] > mxc[i][j+1][k-1]); if (i) row[i][j][k] += row[i-1][j][k]; } } } for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ for (int k = j+2; k < n; k++){ col[i][j][k] = (a[j][i] > mxr[i][j+1][k-1] and a[k][i] > mxr[i][j+1][k-1]); if (i) col[i][j][k] += col[i-1][j][k]; } } } for (int x = 2; x < n; x++){ for (int y = 2; y < m; y++){ for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (row[i+x-1][j][j+y]-row[i][j][j+y] != x-1) continue; if (col[j+y-1][i][i+x]-col[j][i][i+x] != y-1) continue; ans++; } } } } return ans; } // int main () // { // ios::sync_with_stdio(false); // cin.tie(0); // int n, m; // cin >> n >> m; // vector<vector<int>> a(n, vector<int>(m)); // for (int i = 0; i < n; i++){ // for (int j = 0; j < m; j++) cin >> a[i][j]; // } // cout << count_rectangles(a); // }
#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...