#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
const int N=2501;
vector<int> in;
struct segTree{
vector<int> mi;
void init(int l=0,int r=N-1,int i=1)
{
if(i==1)
mi.resize(4*N);
if(l==r)
{
mi[i]=in[l];
return;
}
int m=(l+r)>>1;
init(l,m,2*i);
init(m+1,r,2*i+1);
mi[i]=min(mi[2*i],mi[2*i+1]);
}
int get(int qs,int qe,int l=0,int r=N-1,int i=1)
{
if(qs>r||qe<l)
return INT_MAX;
if(qs<=l&&qe>=r)
return mi[i];
int m=(l+r)>>1;
return min(get(qs,qe,l,m,2*i),get(qs,qe,m+1,r,2*i+1));
}
}r1[N],r2[N],c1[N],c2[N];
int l[N][N],r[N][N],d[N][N],u[N][N];
ll count_rectangles(vector<vector<int> > a)
{
int n=a.size(),m=a[0].size(),sol=0;
vector<pair<int,int> > stk;
for(int i=0;i<n;i++)
{
stk={{INT_MAX,-1}};
for(int j=0;j<m;j++)
{
while(stk.back().f<a[i][j])
stk.pop_back();
l[i][j]=j-stk.back().s-1;
stk.pb({a[i][j],j});
}
stk={{INT_MAX,m}};
for(int j=m-1;j>=0;j--)
{
while(stk.back().f<a[i][j])
stk.pop_back();
r[i][j]=stk.back().s-j-1;
stk.pb({a[i][j],j});
}
}
for(int j=0;j<m;j++)
{
stk={{INT_MAX,-1}};
for(int i=0;i<n;i++)
{
while(stk.back().f<a[i][j])
stk.pop_back();
u[i][j]=i-stk.back().s-1;
stk.pb({a[i][j],j});
}
stk={{INT_MAX,m}};
for(int i=n-1;i>=0;i--)
{
while(stk.back().f<a[i][j])
stk.pop_back();
d[i][j]=stk.back().s-i-1;
stk.pb({a[i][j],j});
}
}
/*for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
printf("%i ",l[i][j]);
printf("\n");
}*/
for(int j=0;j<m;j++)
{
in.clear();
for(int i=0;i<n;i++)
in.pb(l[i][j]);
c1[j].init();
}
for(int j=0;j<m;j++)
{
in.clear();
for(int i=0;i<n;i++)
in.pb(r[i][j]);
c2[j].init();
}
for(int i=0;i<n;i++)
{
in.clear();
for(int j=0;j<m;j++)
in.pb(u[i][j]);
r1[i].init();
}
for(int i=0;i<n;i++)
{
in.clear();
for(int j=0;j<m;j++)
in.pb(d[i][j]);
r2[i].init();
}
for(int i=0;i<n;i++)
{
stk={{INT_MAX,-1}};
for(int j=0;j<m;j++)
{
while(stk.back().f<=a[i][j])
stk.pop_back();
l[i][j]=stk.back().s+1;
stk.pb({a[i][j],j});
}
stk={{INT_MAX,m}};
for(int j=m-1;j>=0;j--)
{
while(stk.back().f<=a[i][j])
stk.pop_back();
r[i][j]=stk.back().s-1;
stk.pb({a[i][j],j});
}
}
for(int j=0;j<m;j++)
{
stk={{INT_MAX,-1}};
for(int i=0;i<n;i++)
{
while(stk.back().f<=a[i][j])
stk.pop_back();
u[i][j]=stk.back().s+1;
stk.pb({a[i][j],j});
}
stk={{INT_MAX,m}};
for(int i=n-1;i>=0;i--)
{
while(stk.back().f<=a[i][j])
stk.pop_back();
d[i][j]=stk.back().s-1;
stk.pb({a[i][j],j});
}
}
for(int i=1;i<n-1;i++)
for(int j=1;j<m-1;j++)
sol+=r[i][j]<n-1&&l[i][j]>0&&u[i][j]>0&&d[i][j]<m-1&&c1[r[i][j]+1].get(u[i][j],d[i][j])>r[i][j]-l[i][j]&&c2[l[i][j]-1].get(u[i][j],d[i][j])>r[i][j]-l[i][j]&&r1[d[i][j]+1].get(l[i][j],r[i][j])>d[i][j]-u[i][j]&&r2[u[i][j]-1].get(l[i][j],r[i][j])>d[i][j]-u[i][j];
return sol;
}
/*int main()
{
freopen("in.txt","r",stdin);
int n,m;
scanf("%i %i",&n,&m);
vector<vector<int> > mat(n,vector<int>(m));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%i",&mat[i][j]);
printf("%lld\n",count_rectangles(mat));
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1528 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
5792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1528 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
5792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1528 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
5792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1528 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
5792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
279 ms |
196948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1528 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
5792 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
