#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
int n,m,l[2501][2501],r[2501][2501],u[2501][2501],d[2501][2501],cnt,nxt[2501][2501][4];
stack <pair <int, int>> st;
vector <pair <pair <int, int>, pair <int, int>>> ve;
long long count_rectangles(vector <vector <int>> a){
n=a.size(),m=a[0].size();
for (int i=0;i<n;i++){
while (!st.empty())
st.pop();
for (int j=0;j<m;j++){
while (!st.empty()&&st.top().first<a[i][j])
st.pop();
l[i][j]=(st.empty()?-1:st.top().second);
st.push({a[i][j],j});
}
while (!st.empty())
st.pop();
for (int j=m-1;j>=0;j--){
while (!st.empty()&&st.top().first<a[i][j])
st.pop();
r[i][j]=(st.empty()||st.top().first==a[i][j]?-1:st.top().second);
st.push({a[i][j],j});
}
}
for (int j=0;j<m;j++){
while (!st.empty())
st.pop();
for (int i=0;i<n;i++){
while (!st.empty()&&st.top().first<a[i][j])
st.pop();
u[i][j]=(st.empty()?-1:st.top().second);
st.push({a[i][j],i});
}
while (!st.empty())
st.pop();
for (int i=n-1;i>=0;i--){
while (!st.empty()&&st.top().first<a[i][j])
st.pop();
d[i][j]=(st.empty()||st.top().first==a[i][j]?-1:st.top().second);
st.push({a[i][j],i});
}
}
for (int i=1;i<n-1;i++)
for (int j=1;j<m-1;j++){
int r1,c1,r2,c2;
r1=u[i+1][j];
c1=j-1;
r2=i+1;
if (r1!=-1)
c2=r[r1+1][c1];
if (r1!=-1&&c2!=-1)
ve.push_back({{r1,r2},{c1,c2}});
c2=j+1;
if (r1!=-1)
c1=l[r1+1][c2];
if (r1!=-1&&c1!=-1)
ve.push_back({{r1,r2},{c1,c2}});
r1=i-1;
c1=j-1;
r2=d[r1][c1+1];
c2=r[r1+1][c1];
if (r2!=-1&&c2!=-1)
ve.push_back({{r1,r2},{c1,c2}});
c2=j+1;
r2=d[r1][c2-1];
c1=l[r1+1][c2];
if (r2!=-1&&c1!=-1)
ve.push_back({{r1,r2},{c1,c2}});
}
memset(nxt,-1,sizeof(nxt));
for (int i=n-1;i>=0;i--)
for (int j=m-1;j>=0;j--){
int k=l[i][j];
if (k!=-1){
nxt[i][j][0]=i;
if (i<n-1){
if (r[i+1][k]==j)
nxt[i][j][0]=nxt[i+1][k][1];
else if (l[i+1][j]==k)
nxt[i][j][0]=nxt[i+1][j][0];
}
}
k=r[i][j];
if (k!=-1){
nxt[i][j][1]=i;
if (i<n-1){
if (l[i+1][k]==j)
nxt[i][j][1]=nxt[i+1][k][0];
else if (r[i+1][j]==k)
nxt[i][j][1]=nxt[i+1][j][1];
}
}
}
for (int j=m-1;j>=0;j--)
for (int i=n-1;i>=0;i--){
int k=u[i][j];
if (k!=-1){
nxt[i][j][2]=j;
if (j<m-1){
if (d[k][j+1]==i)
nxt[i][j][2]=nxt[k][j+1][3];
else if (u[i][j+1]==k)
nxt[i][j][2]=nxt[i][j+1][2];
}
}
k=d[i][j];
if (k!=-1){
nxt[i][j][3]=j;
if (j<m-1){
if (u[k][j+1]==i)
nxt[i][j][3]=nxt[k][j+1][2];
else if (d[i][j+1]==k)
nxt[i][j][3]=nxt[i][j+1][3];
}
}
}
for (auto [p,q]:ve){
auto [r1,r2]=p;
auto [c1,c2]=q;
if (r2-r1>1&&c2-c1>1&&((u[r2][c1+1]==r1&&nxt[r2][c1+1][2]>=c2-1)||(d[r1][c1+1]==r2&&nxt[r1][c1+1][3]>=c2-1))&&((l[r1+1][c2]==c1&&nxt[r1+1][c2][0]>=r2-1)||(r[r1+1][c1]==c2&&nxt[r1+1][c1][1]>=r2-1))){
cnt++;
mp[{p,q}]=0;
}
}
return cnt;
}
Compilation message
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:124:13: error: 'mp' was not declared in this scope; did you mean 'p'?
124 | mp[{p,q}]=0;
| ^~
| p
