이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 2502;
template<class T> struct Seg { // comb(ID,b) = b
T ID = T();
function<T(const T&,const T&)> comb;
int n; vector<T> seg;
void init(int _n, T base, function<T(const T&,const T&)> join) {
n = _n; comb = join; ID = base; seg.assign(2 * n, ID); }
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n - 1] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // sum on interval [l, r]
T ra = ID, rb = ID;
for (l += n-1, r += n; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
void build(vector<T> a) {
for(int i = 1; i <= n; i++) seg[n + i - 1] = a[i - 1];
for(int i = n - 1; i > 0; i--) seg[i] = comb(seg[i << 1], seg[i << 1|1]);
}
};
long long count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
vector<Seg<int>> rows(n);
for(int i = 0; i < n; i++) {
rows[i].init(m, 0, [&] (int x, int y) {
return max(x, y);
});
}
vector<Seg<int>> columns(m);
for(int i = 0; i < m; i++) {
columns[i].init(n, 0, [&] (int x, int y) {
return max(x, y);
});
}
for(int i = 0; i < n; i++)
rows[i].build(a[i]);
for(int j = 0; j < m; j++)
for(int i = 0; i < n; i++)
columns[j].upd(i + 1, a[i][j]);
//cout << "Done till segtree build" << endl;
long long ans = 0;
for(int r1 = 1; r1 < n - 1; r1++) {
for(int c1 = 1; c1 < m - 1; c1++) {
for(int r2 = r1; r2 < n - 1; r2++) {
for(int c2 = c1; c2 < m - 1; c2++) {
//if(r1 == r2 && c1 == c2) continue;
bool flag = 1;
for(int i = r1; i <= r2; i++)
flag &= (rows[i].query(c1 + 1, c2 + 1) < min(a[i][c1 - 1], a[i][c2 + 1]));
for(int i = c1; i <= c2; i++)
flag &= (columns[i].query(r1 + 1, r2 + 1) < min(a[r1 - 1][i], a[r2 + 1][i]));
ans += flag;
}
}
}
}
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... |