#include "rect.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define pb push_back
#define vi vector<int>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define pii pair<int,int>
#define vpii vector<pii>
#define vb vector<bool>
#define mp make_pair
using namespace std;
int n,m;
vector<vector<signed>>grid;
vpii adj(pii a){
int x = a.first; int y = a.second;
vpii ret;
if(x > 0 && grid[x-1][y] == 0){
ret.pb(mp(x-1, y));
}
if(y > 0 && grid[x][y-1] == 0){
ret.pb(mp(x, y-1));
}
if(x < n-1 && grid[x+1][y] == 0){
ret.pb(mp(x+1, y));
}
if(y < m-1 && grid[x][y+1] == 0){
ret.pb(mp(x, y+1));
}
return ret;
}
long long int count_rectangles(std::vector<std::vector<signed> > a) {
grid = a;
n = a.size(); m = a[0].size();
//subtask 5
if(n < 3)return 0;
else{
int ans = 0;
vi v;
f0r(i,m){
if(a[0][i] > a[1][i] && a[1][i] < a[2][i])v.pb(1);
else v.pb(0);
}
vi ps(m+1);
FOR(i, 1, m+1){
ps[i] = ps[i-1] + v[i-1];
}
f0r(i, n){
int run = -1;
FOR(j, i+1, n){
if(run < a[1][j]){
run = a[1][j];
if(j != i + 1 && ps[j] - ps[i+1] == (j - i))ans++;
}
if(a[1][j] >= a[1][i]){
break;
}
}
}
return ans;
}
//subtask 6
/*
vector<vector<bool>>vis(n, vector<bool>(m));
int ans = 0;
f0r(i,n){
f0r(j,m){
if(a[i][j] == 0 && !vis[i][j]){
queue<pii>q;
int tot = 1;
q.push(mp(i,j));
// cout<<i<<' '<<j<<'\n';
vis[i][j] = 1;
int mnx = i; int mxx = i; int mny = j; int mxy = j;
while(!q.empty()){
pii node = q.front(); q.pop();
for(auto u : adj(node)){
if(vis[u.first][u.second])continue;
// cout<<u.first<<' '<<u.second<<'\n';
mnx = min(mnx, u.first);
mxx = max(mxx, u.first);
mny = min(mny, u.second);
mxy = max(mxy, u.second);
tot++;
vis[u.first][u.second] = 1;
q.push(mp(u.first, u.second));
}
}
int area = (mxx - mnx + 1) * (mxy - mny + 1);
// cout<<"FINAL"<<' '<<area<<' '<<tot<<'\n';
if(mnx > 0 && mxx < n-1 && mny > 0 && mxy < m-1 && area == tot)ans++;
}
}
}
return ans;
*/
}
