이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = (int) a.size(), m = (int) a[0].size();
vector<vii> segs(n);
for (int i = 1; i < n - 1; i++) {
for (int j = 0; j < m - 2; j++) {
int mx = -1;
for (int k = j + 1; k < m - 1; k++) {
mx = max(mx, a[i][k]);
if (min(a[i][j], a[i][k + 1]) > mx) segs[i].emplace_back(j, k + 1);
}
}
}
int seg_cnt[m][m];
ll ans = 0;
for (int r1 = 0; r1 < n - 2; r1++) {
vector<int> vert_mx(m, -1);
memset(seg_cnt, 0, sizeof seg_cnt);
for (int r2 = r1 + 2; r2 < n; r2++) {
for (int c = 0; c < m; c++) vert_mx[c] = max(vert_mx[c], a[r2 - 1][c]);
vector<int> pre(m, 0);
for (int c = 1; c < m - 1; c++) {
if (min(a[r1][c], a[r2][c]) > vert_mx[c]) pre[c] = 1;
pre[c] += pre[c - 1];
}
pre[m - 1] = pre[m - 2];
for (auto &[l, r] : segs[r2 - 1]) {
if (++seg_cnt[l][r] == r2 - r1 - 1 && pre[r - 1] - pre[l] == r - l - 1) {
//cerr << r1 << ' ' << r2 << ' ' << l << ' ' << r << endl;
ans++;
}
}
}
}
return ans;
}
# | 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... |