| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1077453 | Ignut | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Ignut
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 123;
const int N = 777;
int min_h[N][N], max_h[N][N], min_v[N][N], max_v[N][N];
int minH[N][N][N], maxH[N][N][N], minV[N][N][N], maxV[N][N][N];
ll count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++) {
for (int ii = i; ii >= 0; ii --) {
if (a[ii][j] > a[i][j]) break;
min_v[i][j] = ii;
}
for (int ii = i; ii < n; ii ++) {
if (a[ii][j] > a[i][j]) break;
max_v[i][j] = ii;
}
for (int jj = j; jj >= 0; jj --) {
if (a[i][jj] > a[i][j]) break;
min_h[i][j] = jj;
}
for (int jj = j; jj < m; jj ++) {
if (a[i][jj] > a[i][j]) break;
max_h[i][j] = jj;
}
}
}
for (int j = 0; j < m; j ++) {
for (int l = 0; l < n; l ++) {
minH[j][l][l] = min_h[l][j];
maxH[j][l][l] = max_h[l][j];
minV[j][l][l] = min_v[l][j];
maxV[j][l][l] = max_v[l][j];
for (int r = l + 1; r < n; r ++) {
minH[j][l][r] = min(minH[j][l][r - 1], min_h[r][j]);
maxH[j][l][r] = max(maxH[j][l][r - 1], max_h[r][j]);
minV[j][l][r] = min(minV[j][l][r - 1], min_v[r][j]);
maxV[j][l][r] = max(maxV[j][l][r - 1], max_v[r][j]);
}
}
}
int res = 0;
for (int u = 1; u < n - 1; u ++) {
for (int d = u; d < n - 1; d ++) {
for (int l = 1; l < m - 1; l ++) {
int mnh = INF, mxh = -INF, mnv = INF, mxv = -INF;
for (int r = l; r < m - 1; r ++) {
mnh = min(mnh, minH[r][u][d]);
mxh = max(mxh, maxH[r][u][d]);
mnv = min(mnv, minV[r][u][d]);
mxv = max(mxv, maxV[r][u][d]);
if (mnh < l) break;
if (mnv < u) break;
if (mxv > d) break;
res += (mxh == r);
}
}
}
}
return res;
}