#include "rect.h"
#include <bits/stdc++.h>
#define ent '\n'
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
using namespace std;
const int maxn = 2512;
vector<short> gx[maxn][maxn], gy[maxn][maxn];
vector<pair<short, short>> cnt[maxn][maxn];
short lx[maxn][maxn], rx[maxn][maxn];
int t[maxn];
int n, m;
void upd(int i, int x) {
for(; i >= 0; i = (i & (i + 1)) - 1) {
t[i] += x;
}
}
int get(int i) {
int ans = 0;
for(; i < maxn; i |= (i + 1)) {
ans += t[i];
}
return ans;
}
long long count_rectangles(vector<vector<int>> a) {
n = (int)a.size(), m = (int)a[0].size();
for(int j = 0; j < m; j++) {
stack<int> s;
for(int i = 0; i < n; i++) {
while(!s.empty() && a[s.top()][j] < a[i][j]) {
s.pop();
}
lx[i][j] = -1;
if(!s.empty()) {
lx[i][j] = s.top();
gy[s.top()][j].push_back(i);
}
s.push(i);
}
while(!s.empty()) {
s.pop();
}
for(int i = n - 1; i >= 0; i--) {
while(!s.empty() && a[s.top()][j] < a[i][j]) {
s.pop();
}
rx[i][j] = n;
if(!s.empty()) {
rx[i][j] = s.top();
if(lx[s.top()][j] != i) gy[i][j].push_back(s.top());
}
s.push(i);
}
}
auto checkX = [&] (int i, int l, int r) -> bool {
if(l > r || l < 0 || r >= m | i < 0 || i >= n) return false;
return (rx[i][l] == r || lx[i][r] == l);
};
auto checkY = [&](int j, int l, int r) {
if(l > r || l < 0 || r >= n || j < 0 || j >= m) return false;
return (rx[l][j] == r || lx[r][j] == l);
};
long long ans = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
sort(gy[i][j].begin(), gy[i][j].end());
}
}
for(int i = 0; i < n; i++) {
stack<int> s;
for(int j = 0; j < m; j++) {
while(!s.empty() && a[i][s.top()] < a[i][j]) {
s.pop();
}
lx[i][j] = -1;
if(!s.empty()) {
lx[i][j] = s.top();
gx[i][s.top()].push_back(j);
}
s.push(j);
}
while(!s.empty()) {
s.pop();
}
for(int j = m - 1; j >= 0; j--) {
while(!s.empty() && a[i][s.top()] < a[i][j]) {
s.pop();
}
rx[i][j] = m;
if(!s.empty()) {
rx[i][j] = s.top();
if(lx[i][s.top()] != j) gx[i][j].push_back(s.top());
}
s.push(j);
}
}
for(int i = 0; i < n; i++) {
for(int l = 0; l < m; l++) {
for(int r : gx[i][l]) {
if(r - l <= 1) continue;
if(checkX(i - 1, l, r)) {
continue;
}
int ptr = i;
while(ptr + 1 < n && checkX(ptr + 1, l, r)) {
ptr++;
}
for(int x = i - 1; x < ptr; x++) {
int pos = upper_bound(gy[x][l + 1].begin(), gy[x][l + 1].end(), ptr + 1) - gy[x][l + 1].begin() - 1;
if(pos >= 0) {
cnt[x][l + 1].push_back({pos, r - 1});
}
}
}
}
}
for(int j = 0; j < m; j++) {
stack<int> s;
for(int i = 0; i < n; i++) {
gx[i][j] = vector<short> (gy[i][j].size(), -1);
while(!s.empty() && a[s.top()][j] < a[i][j]) {
s.pop();
}
lx[i][j] = -1;
if(!s.empty()) {
lx[i][j] = s.top();
}
s.push(i);
}
while(!s.empty()) {
s.pop();
}
for(int i = n - 1; i >= 0; i--) {
while(!s.empty() && a[s.top()][j] < a[i][j]) {
s.pop();
}
rx[i][j] = n;
if(!s.empty()) {
rx[i][j] = s.top();
}
s.push(i);
}
}
for(int j = 0; j < m; j++) {
for(int l = 0; l < n; l++) {
for(int r : gy[l][j]) {
if(r - l <= 1) continue;
if(checkY(j - 1, l, r)) {
continue;
}
int ptr = j;
while(ptr + 1 < m && checkY(ptr + 1, l, r)) {
ptr++;
}
for(int x = j; x <= ptr; x++) {
int pos = lower_bound(gy[l][x].begin(), gy[l][x].end(), r) - gy[l][x].begin();
gx[l][x][pos] = ptr;
}
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
sort(cnt[i][j].begin(), cnt[i][j].end());
for(int pos = 0, ptr = 0; pos < gy[i][j].size(); pos++) {
upd(gx[i][j][pos], 1);
while(ptr < cnt[i][j].size() && cnt[i][j][ptr].first == pos) {
ans += get(cnt[i][j][ptr].second);
ptr++;
}
}
for(int pos : gx[i][j]) {
upd(pos, -1);
}
}
}
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... |