이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1; // PAMIETAC, ZE TAM MAM CIAG INDEKSOWANY OD 0
struct segminmax{
int base;
struct Node{
int mn, mx;
Node(){ mn = inf, mx = 0; }
};
vv<Node> t;
void init(int n, vv<int> &a, vv<int> &b){
base = 1;
while(base < n) base <<= 1;
t.resize(base<<1, Node());
for(int i = 1; i <= n; ++i) t[i+base-1].mn = b[i-1], t[i+base-1].mx = a[i-1];
for(int i = base-1; i; --i) t[i].mn = min(t[i<<1].mn, t[i<<1|1].mn), t[i].mx = max(t[i<<1].mx, t[i<<1|1].mx);
}
pii query_interval(int i, int s, int e, int x, int y){
if(x <= s && e <= y) return pii(t[i].mn, t[i].mx);
int mid = (s+e)>>1; pii result = pii(inf, 0), tmp;
if(x <= mid) tmp = query_interval(i<<1, s, mid, x, y), result.fi = min(result.fi, tmp.fi), result.se = max(result.se, tmp.se);
if(mid < y) tmp = query_interval(i<<1|1, mid+1, e, x, y), result.fi = min(result.fi, tmp.fi), result.se = max(result.se, tmp.se);
return result;
}
pii query(int l, int r){
if(l <= r) return query_interval(1, 1, base, max(1, l), min(base, r));
return pii(inf, 0);
}
};
struct seg{
int base;
vv<int> t;
void init(int n){
base = 1;
while(base < n) base <<= 1;
t.resize(base<<1, 0);
}
void update(int i, int val){
for(i += base-1, t[i] = val, i >>= 1; i; i >>= 1) t[i] = t[i<<1]+t[i<<1|1];
}
int query_interval(int i, int s, int e, int x, int y){
if(x <= s && e <= y) return t[i];
int mid = (s+e)>>1, result = 0;
if(x <= mid) result += query_interval(i<<1, s, mid, x, y);
if(mid < y) result += query_interval(i<<1|1, mid+1, e, x, y);
return result;
}
int query(int l, int r){
if(l <= r) return query_interval(1, 1, base, max(1, l), min(base, r));
return 0;
}
};
ll count_rectangles(vv<vv<int>> t){
int n = ssize(t), m = ssize(t[0]);
vv<vv<int>> u(n, vv<int>(m, 0)), d(n, vv<int>(m, n-1));
vv<map<pii, int>> mp(n);
vv<int> st;
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){ // przedzialy gdzie ja to prawy koniec
while(ssize(st) && t[i][st.back()] < t[i][j]) st.pop_back();
if(ssize(st)) mp[i][pii(st.back(), j)] = 1;
st.emplace_back(j);
} st = vv<int>();
for(int j = m-1; ~j; --j){ // przedzialy gdzie ja to lewy koniec
while(ssize(st) && t[i][st.back()] < t[i][j]) st.pop_back();
if(ssize(st)) mp[i][pii(j, st.back())] = 1;
st.emplace_back(j);
} st = vv<int>();
}
for(int j = 0; j < m; ++j){
for(int i = 0; i < n; ++i){ // przedzialy gdzie ja to dolny koniec (ustawiamy najblizszego do gory)
while(ssize(st) && t[st.back()][j] < t[i][j]) st.pop_back();
if(ssize(st)) u[i][j] = st.back();
st.emplace_back(i);
} st = vv<int>();
for(int i = n-1; ~i; --i){ // przedzialy gdzie ja to gorny koniec (ustawiamy najblizszego na dole)
while(ssize(st) && t[st.back()][j] < t[i][j]) st.pop_back();
if(ssize(st)) d[i][j] = st.back();
st.emplace_back(i);
} st = vv<int>();
}
//~ for(int i = 0; i < n; ++i){
//~ for(int j = 0; j < m; ++j) printf("%d ", d[i][j]);
//~ pn;
//~ }
ll result = 0;
vv<segminmax> segm(n);
vv<vv<int>> rem(n+1);
seg seg; seg.init(n);
vv<pii> queries;
for(int i = 0; i < n; ++i) segm[i].init(m, u[i], d[i]);
for(int i = 1; i < n-1; ++i){
for(pair<pii, int> pd : mp[i]) if(pd.se){
int l = pd.fi.fi+1, r = pd.fi.se-1;
if(r < l) continue;
++l, ++r; // do przedzialowca
int sz = 1;
for(int j = i+1; j < n-1; ++j) if(mp[j][pd.fi]) ++sz, mp[j][pd.fi] = 0;
else break;
queries.resize(sz+2);
for(int j = i-1; j <= i+sz; ++j) queries[j-(i-1)] = segm[j].query(l, r);
for(int j = i; j < i+sz; ++j){
//~ printf("%d %d %d: %lld\n", j, l-1, r-1, result);
for(int &x : rem[j-i]) seg.update(x, 0);
rem[j-i].clear();
int endpoint = queries[j-1-i+1].fi;
if(j < endpoint){
seg.update(j-i+1, 1);
rem[min(sz, endpoint-i)].emplace_back(j-i+1);
}
endpoint = queries[j+1-i+1].se;//segm[j+1].query_max(l, r);
result += seg.query(max(-1, endpoint-i)+2, j-i+1);
//~ printf("%d %d %d: %d %lld\n", j, l-1, r-1, endpoint, result);
}
for(int &x : rem[sz]) seg.update(x, 0);
rem[sz].clear(), queries.clear();
}
}
return result;
}
#ifdef LOCAL
int main(){
int T = 1;
for(++T; --T; ){
int n, m; scanf("%d%d", &n, &m);
vv<vv<int>> t(n, vv<int>(m, 0));
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j) scanf("%d", &t[i][j]);
ll result = count_rectangles(t);
printf("%lld\n", result);
}
return 0;
}
#endif
# | 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... |