This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define range(i, m, n) for(int i = m; i < n; i++)
#define husk(i, m, n) for(int i = m; i > n; i--)
struct sp {
vector<int> st;
unordered_set<int> alive;
sp(){};
void add(int ss) {
st.push_back(ss);
alive.insert(ss);
}
int pos(int ss) {
return upper_bound(st.begin(), st.end(), ss, greater<int>()) - st.begin();
}
};
long long count_rectangles(vector<vector<int>> a) {
int m = a.front().size();
int n = a.size();
auto pos = [&] (vector<int> cur) {
int s = cur.size();
vector<pair<int, int>> res;
vector<int> st;
range(i, 0, s) {
while(st.size() && cur[st.back()] <= cur[i]) {
if(st.back() < i - 1) res.emplace_back(st.back() + 1, i - 1);
int b = st.back();
st.pop_back();
if(cur[b] == cur[i]) goto A;
}
if(st.size() && st.back() < i - 1) res.emplace_back(st.back() + 1, i - 1);
A:;
st.push_back(i);
}
return res;
};
vector<vector<sp>> cur(n, vector<sp>(m));
range(i, 0, n) {
vector<pair<int, int>> ss = pos(a[i]);
for(auto j : ss) {
cur[i][j.second].add(j.first);
}
}
auto cross = [&](sp &a, sp &b) {
sp res;
for(auto i : (a.st.size() < b.st.size() ? a.st : b.st)) {
if((a.st.size() < b.st.size() ? b.alive : a.alive).count(i)) res.add(i);
}
return res;
};
long long res = 0;
vector<vector<pair<int, int>>> to(n, vector<pair<int, int>> (n, make_pair(-2, -2)));
range(i, 0, m) {
vector<int> psy(n);
range(j, 0, n) psy[j] = a[j][i];
vector<pair<int, int>> ss = pos(psy);
int sz = ss.size();
vector<sp> dp(sz);
vector<int> pr(n, -1);
range(j, 0, sz) {
int p = ss[j].second;
dp[j] = cur[p][i];
while(p >= ss[j].first) {
if(~pr[p]) {
dp[j] = cross(dp[i], dp[pr[p]]);
p = ss[pr[p]].first - 1;
} else {
dp[j] = cross(dp[i], cur[p][i]);
p--;
}
}
pr[ss[j].second] = j;
int l = to[ss[j].first][ss[j].second].second == i - 1 ? to[ss[j].first][ss[j].second].first : i;
if(l == i) to[ss[j].first][ss[j].second] = make_pair(i, i);
to[ss[j].first][ss[j].second].second = i;
res += dp[j].pos(l);
}
}
return res;
}
# | 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... |