이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
int ri() {
int n;
scanf("%d", &n);
return n;
}
struct SegTree {
int n;
std::vector<int> data;
SegTree (int n_) {
for (n = 1; n < n_; n <<= 1);
data.resize(n << 1);
}
void add(int i, int val) {
for (i += n; i; i >>= 1) data[i] += val;
}
int sum(int l, int r) {
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (r & 1) res += data[--r];
if (l & 1) res += data[l++];
}
return res;
}
};
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size();
int m = a[0].size();
assert(n <= 700 && m <= 700);
std::vector<std::vector<std::vector<int> > > r0(n, std::vector<std::vector<int> > (m));
for (int i = 1; i + 1 < n; i++) {
bool ok[n][m];
std::vector<int> max(m, -1);
for (int j = i + 1; j < n; j++) {
for (int k = 1; k + 1 < m; k++) {
max[k] = std::max(max[k], a[j - 1][k]);
ok[j][k] = max[k] < a[j][k] && max[k] < a[i - 1][k];
}
}
std::vector<int> cur(n, 0);
for (int j = m - 2; j >= 1; j--) {
for (int k = i + 1; k < n; k++) {
if (ok[k][j]) cur[k]++;
else cur[k] = 0;
}
r0[i][j] = std::vector<int>(cur.begin() + i, cur.end());
/*
std::cerr << "r0 " << i << " " << j << " : ";
for (auto k : r0[i][j]) std::cerr << k << " ";
std::cerr << std::endl;*/
}
}
std::vector<std::vector<std::vector<int> > > r1(n, std::vector<std::vector<int> > (m));
for (int i = 1; i + 1 < m; i++) {
bool ok[n][m];
std::vector<int> max(n, -1);
for (int j = i + 1; j < m; j++) {
for (int k = 1; k + 1 < n; k++) {
max[k] = std::max(max[k], a[k][j - 1]);
ok[k][j] = max[k] < a[k][j] && max[k] < a[k][i - 1];
}
}
std::vector<int> cur(m, 0);
for (int j = n - 2; j >= 1; j--) {
for (int k = i + 1; k < m; k++) {
if (ok[j][k]) cur[k]++;
else cur[k] = 0;
}
r1[j][i] = std::vector<int>(cur.begin() + i, cur.end());
/*
std::cerr << "r1 " << j << " " << i << " : ";
for (auto k : r1[j][i]) std::cerr << k << " ";
std::cerr << std::endl;*/
}
}
int64_t res = 0;
for (int i = 1; i + 1 < n; i++) {
for (int j = 1; j + 1 < m; j++) {
std::vector<int> all[m];
for (int k = 1; k < (int) r0[i][j].size(); k++) all[r0[i][j][k]].push_back(k);
SegTree tree(n);
for (int k = 1; k < m; k++) {
if (k < (int) r1[i][j].size()) tree.add(r1[i][j][k], 1);
for (auto l : all[k]) {
res += tree.sum(l, tree.n);
/*
int t = tree.sum(l, tree.n);
if (t) std::cerr << i << " " << j << " " << k << " " << l << " " << t << std::endl;*/
}
}
}
}
return res;
}
#ifdef LOCAL
int main() {
int n = ri();
int m = ri();
std::vector<std::vector<int> > a(n, std::vector<int>(m));
for (auto &i : a) for (auto &j : i) j = ri();
printf("%lld\n", count_rectangles(a));
return 0;
}
#endif
컴파일 시 표준 에러 (stderr) 메시지
rect.cpp: In function 'int ri()':
rect.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
# | 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... |