이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> pref;
int query(int r1, int c1, int r2, int c2) {
int val = pref[r2][c2];
val -= (c1? pref[r2][c1 - 1]: 0);
val -= (r1? pref[r1 - 1][c2]: 0);
val += (c1 && r1? pref[r1 - 1][c1 - 1]: 0);
return val;
}
long long count_rectangles(vector<vector<int>> grid) {
int n = grid.size();
int m = grid[0].size();
int maxi = -1;
for (int i = 0; i < n; i++) maxi = max(maxi, *max_element(grid[i].begin(), grid[i].end()));
if (maxi <= 1) {
// Subtask 6
pref.resize(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
int prefhere = 0;
for (int j = 0; j < m; j++) {
prefhere += grid[i][j];
pref[i][j] = (i? pref[i - 1][j]: 0) + prefhere;
}
}
vector<vector<int>> left(n, vector<int>(m, -1));
vector<vector<int>> above(n, vector<int>(m, -1));
for (int i = 0; i < n; i++) {
int here = -1;
for (int j = 0; j < m; j++) {
if (grid[i][j]) here = j;
left[i][j] = here;
}
}
for (int j = 0; j < m; j++) {
int here = -1;
for (int i = 0; i < n; i++) {
if (grid[i][j]) here = i;
above[i][j] = here;
}
}
long long ans = 0;
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < m - 1; j++) {
if (!grid[i][j] && grid[i + 1][j] && grid[i][j + 1] && left[i][j] != -1 && above[i][j] != -1) {
int l = left[i][j];
int t = above[i][j];
int bottom = query(i + 1, l + 1, i + 1, j);
int top = query(t, l + 1, t, j);
int leftside = query(t + 1, l, i, l);
int rightside = query(t + 1, j + 1, i, j + 1);
int inside = query(t + 1, l + 1, i, j);
if (bottom == j - l && top == j - l && leftside == i - t && rightside == i - t && !inside) ans++;
}
}
}
return ans;
} else if (n == 3) {
long long ans = 0;
for (int j = 1; j < m - 1; j++) {
int maxi = -1;
for (int k = j; k < m - 1; k++) {
if (grid[1][k] >= min(grid[0][k], grid[2][k])) break;
maxi = max(maxi, grid[1][k]);
if (maxi < min(grid[1][j - 1], grid[1][k + 1])) ans++;
}
}
return ans;
} else if (max(n, m) <= 30) {
long long ans = 0;
for (int j = 1; j < m - 1; j++) {
for (int k = j; k < m - 1; k++) {
for (int i = 1; i < n - 1; i++) {
vector<int> maxi(k - j + 1, -1);
for (int r = i; r < n - 1; r++) {
bool here = true;
for (int l = j; l <= k; l++) {
if (grid[r][l] >= min(grid[r][j - 1], grid[r][k + 1])) here = false;
maxi[l - j] = max(maxi[l - j], grid[r][l]);
}
if (!here) break;
for (int l = j; l <= k; l++) {
if (maxi[l - j] >= min(grid[i - 1][l], grid[r + 1][l])) here = false;
}
if (here) ans++;
}
}
}
}
return ans;
}
return 0; // for subtasks I'm not solving. (or n is 1 or 2)
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |