| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1077453 | Ignut | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 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;
}