#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef array<array<array<array<int, 3>, 3>, 3>, 3> pi4;
const int MAXN = 5e4;
int N, M;
vector<vector<int>> A;
vector<vector<pi4>> P1, P2, S1, S2, H1, H2, V1, V2;
vector<int> B11, B12, B21, B22;
inline bool isin(int i, int j, int li, int ri, int lj, int rj)
{
return li<=i && i<=ri && lj<=j && j<=rj;
}
inline int getout(int i, int j, int li, int ri, int lj, int rj)
{
if(!isin(i, j, li, ri, lj, rj)) return 5;
pii ret={0, 4};
if(isin(i-1, j, li, ri, lj, rj) && A[i-1][j]<A[i][j]) ret=max(ret, pii(A[i-1][j], 0));
if(isin(i+1, j, li, ri, lj, rj) && A[i+1][j]<A[i][j]) ret=max(ret, pii(A[i+1][j], 1));
if(isin(i, j-1, li, ri, lj, rj) && A[i][j-1]<A[i][j]) ret=max(ret, pii(A[i][j-1], 2));
if(isin(i, j+1, li, ri, lj, rj) && A[i][j+1]<A[i][j]) ret=max(ret, pii(A[i][j+1], 3));
return ret.second;
}
inline int query(vector<vector<pi4>> &S, int pi, int qi, int pj, int qj, int li, int ri, int lj, int rj)
{
return S[ri][rj][pi][qi][pj][qj]-S[li-1][rj][pi][qi][pj][qj]-S[ri][lj-1][pi][qi][pj][qj]+S[li-1][lj-1][pi][qi][pj][qj];
}
int naive(int li, int ri, int lj, int rj)
{
vector<pair<int, pii>> V;
for(int i=li; i<=ri; i++) for(int j=lj; j<=rj; j++) V.push_back({A[i][j], {i, j}});
sort(V.begin(), V.end());
for(int i=1; i<V.size(); i++) if(abs(V[i].second.first-V[i-1].second.first)+abs(V[i].second.second-V[i-1].second.second)!=1) return false;
return true;
}
ll ans=0;
void solve()
{
map<pii, int> MM;
for(int i=4; i<=M; i++)
{
MM[{B11[i-3], B21[i-3]}]++;
int t1=1-B12[i], t2=1-B22[i];
ans+=MM[{t1, t2}];
//printf("%d : %d\n", i, MM[{t1, t2}]);
}
}
int main()
{
scanf("%d%d", &N, &M);
if(N<=M)
{
A=vector<vector<int>>(N+2, vector<int>(M+2));
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%d", &A[i][j]);
}
else
{
swap(N, M);
A=vector<vector<int>>(N+2, vector<int>(M+2));
for(int i=1; i<=M; i++) for(int j=1; j<=N; j++) scanf("%d", &A[j][i]);
}
P1=P2=S1=S2=H1=H2=V1=V2=vector<vector<pi4>>(N+2, vector<pi4>(M+2));
for(int i=1; i<=N; i++)
{
for(int j=1; j<=M; j++)
{
for(int pi=0; pi<3; pi++) for(int qi=0; qi<3; qi++)
{
for(int pj=0; pj<3; pj++) for(int qj=0; qj<3; qj++)
{
int li=i-pi, ri=i+qi, lj=j-pj, rj=j+qj;
if(!(1<=li && ri<=N && 1<=lj && rj<=M)) continue;
if(getout(i, j, li, ri, lj, rj)>=4) P1[i][j][pi][qi][pj][qj]=1;
int cnt=0;
if(getout(i-1, j, li, ri, lj, rj)==1) cnt++;
if(getout(i+1, j, li, ri, lj, rj)==0) cnt++;
if(getout(i, j-1, li, ri, lj, rj)==3) cnt++;
if(getout(i, j+1, li, ri, lj, rj)==2) cnt++;
if(cnt!=1) P2[i][j][pi][qi][pj][qj]=1;
}
}
}
}
for(int i=1; i<=N; i++)
{
for(int j=1; j<=M; j++)
{
for(int pi=0; pi<3; pi++) for(int qi=0; qi<3; qi++)
{
for(int pj=0; pj<3; pj++) for(int qj=0; qj<3; qj++)
{
S1[i][j][pi][qi][pj][qj]=P1[i][j][pi][qi][pj][qj]+S1[i-1][j][pi][qi][pj][qj]+S1[i][j-1][pi][qi][pj][qj]-S1[i-1][j-1][pi][qi][pj][qj];
S2[i][j][pi][qi][pj][qj]=P2[i][j][pi][qi][pj][qj]+S2[i-1][j][pi][qi][pj][qj]+S2[i][j-1][pi][qi][pj][qj]-S2[i-1][j-1][pi][qi][pj][qj];
H1[i][j][pi][qi][pj][qj]=P1[i][j][pi][qi][pj][qj]+H1[i][j-1][pi][qi][pj][qj];
H2[i][j][pi][qi][pj][qj]=P2[i][j][pi][qi][pj][qj]+H2[i][j-1][pi][qi][pj][qj];
V1[i][j][pi][qi][pj][qj]=P1[i][j][pi][qi][pj][qj]+V1[i-1][j][pi][qi][pj][qj];
V2[i][j][pi][qi][pj][qj]=P2[i][j][pi][qi][pj][qj]+V2[i-1][j][pi][qi][pj][qj];
}
}
}
}
for(int i=1; i<=N; i++) for(int j=i; j<=N; j++)
{
B11=B12=B21=B22=vector<int>(M+2);
if(i==j)
{
ans+=M+M-1;
for(int k=3; k<=M; k++) if((A[i][k-2]>A[i][k-1] && A[i][k-1]>A[i][k]) || (A[i][k-2]<A[i][k-1] && A[i][k-1]<A[i][k])) ans++;
for(int k=1; k<=M; k++)
{
if(k+1<=M) B11[k]+=P1[i][k][0][0][0][2]+P1[i][k+1][0][0][1][2]-H1[i][k+1][0][0][2][2];
if(k-2>=0) B12[k]+=P1[i][k][0][0][2][0]+P1[i][k-1][0][0][2][1]+H1[i][k-2][0][0][2][2];
if(k+1<=M) B21[k]+=P2[i][k][0][0][0][2]+P2[i][k+1][0][0][1][2]-H2[i][k+1][0][0][2][2];
if(k-2>=0) B22[k]+=P2[i][k][0][0][2][0]+P2[i][k-1][0][0][2][1]+H2[i][k-2][0][0][2][2];
}
//printf("!%d\n", i);
//for(int k=1; k<=M; k++) printf("%d : %d %d %d %d\n", k, B11[k], B12[k], B21[k], B22[k]);
solve();
}
else if(i+1==j)
{
ans+=M;
for(int k=2; k<=M; k++) ans+=naive(i, j, k-1, k);
for(int k=3; k<=M; k++) ans+=naive(i, j, k-2, k);
for(int k=1; k<=M; k++)
{
if(k+1<=M) B11[k]+=P1[i][k][0][1][0][2]+P1[i][k+1][0][1][1][2]-H1[i][k+1][0][1][2][2];
if(k-2>=0) B12[k]+=P1[i][k][0][1][2][0]+P1[i][k-1][0][1][2][1]+H1[i][k-2][0][1][2][2];
if(k+1<=M) B21[k]+=P2[i][k][0][1][0][2]+P2[i][k+1][0][1][1][2]-H2[i][k+1][0][1][2][2];
if(k-2>=0) B22[k]+=P2[i][k][0][1][2][0]+P2[i][k-1][0][1][2][1]+H2[i][k-2][0][1][2][2];
if(k+1<=M) B11[k]+=P1[i+1][k][1][0][0][2]+P1[i+1][k+1][1][0][1][2]-H1[i+1][k+1][1][0][2][2];
if(k-2>=0) B12[k]+=P1[i+1][k][1][0][2][0]+P1[i+1][k-1][1][0][2][1]+H1[i+1][k-2][1][0][2][2];
if(k+1<=M) B21[k]+=P2[i+1][k][1][0][0][2]+P2[i+1][k+1][1][0][1][2]-H2[i+1][k+1][1][0][2][2];
if(k-2>=0) B22[k]+=P2[i+1][k][1][0][2][0]+P2[i+1][k-1][1][0][2][1]+H2[i+1][k-2][1][0][2][2];
}
solve();
}
else if(i+2==j)
{
for(int k=1; k<=M; k++) ans+=naive(i, j, k, k);
for(int k=2; k<=M; k++) ans+=naive(i, j, k-1, k);
for(int k=3; k<=M; k++) ans+=naive(i, j, k-2, k);
for(int k=1; k<=M; k++)
{
if(k+1<=M) B11[k]+=P1[i][k][0][2][0][2]+P1[i][k+1][0][2][1][2]-H1[i][k+1][0][2][2][2];
if(k-2>=0) B12[k]+=P1[i][k][0][2][2][0]+P1[i][k-1][0][2][2][1]+H1[i][k-2][0][2][2][2];
if(k+1<=M) B21[k]+=P2[i][k][0][2][0][2]+P2[i][k+1][0][2][1][2]-H2[i][k+1][0][2][2][2];
if(k-2>=0) B22[k]+=P2[i][k][0][2][2][0]+P2[i][k-1][0][2][2][1]+H2[i][k-2][0][2][2][2];
if(k+1<=M) B11[k]+=P1[i+1][k][1][1][0][2]+P1[i+1][k+1][1][1][1][2]-H1[i+1][k+1][1][1][2][2];
if(k-2>=0) B12[k]+=P1[i+1][k][1][1][2][0]+P1[i+1][k-1][1][1][2][1]+H1[i+1][k-2][1][1][2][2];
if(k+1<=M) B21[k]+=P2[i+1][k][1][1][0][2]+P2[i+1][k+1][1][1][1][2]-H2[i+1][k+1][1][1][2][2];
if(k-2>=0) B22[k]+=P2[i+1][k][1][1][2][0]+P2[i+1][k-1][1][1][2][1]+H2[i+1][k-2][1][1][2][2];
if(k+1<=M) B11[k]+=P1[i+2][k][2][0][0][2]+P1[i+2][k+1][2][0][1][2]-H1[i+2][k+1][2][0][2][2];
if(k-2>=0) B12[k]+=P1[i+2][k][2][0][2][0]+P1[i+2][k-1][2][0][2][1]+H1[i+2][k-2][2][0][2][2];
if(k+1<=M) B21[k]+=P2[i+2][k][2][0][0][2]+P2[i+2][k+1][2][0][1][2]-H2[i+2][k+1][2][0][2][2];
if(k-2>=0) B22[k]+=P2[i+2][k][2][0][2][0]+P2[i+2][k-1][2][0][2][1]+H2[i+2][k-2][2][0][2][2];
}
solve();
}
else
{
for(int k=1; k<=M; k++)
{
int t1=0, t2=0;
t1+=P1[i][k][0][2][0][0]+P1[i+1][k][1][2][0][0]+P1[j-1][k][2][1][0][0]+P1[j][k][2][0][0][0]+V1[j-2][k][2][2][0][0]-V1[i+1][k][2][2][0][0];
t2+=P2[i][k][0][2][0][0]+P2[i+1][k][1][2][0][0]+P2[j-1][k][2][1][0][0]+P2[j][k][2][0][0][0]+V2[j-2][k][2][2][0][0]-V2[i+1][k][2][2][0][0];
if(t1==1 && t2==1) ans++;
}
for(int k=1; k<=M-1; k++)
{
int t1=0, t2=0;
t1+=P1[i][k][0][2][0][1]+P1[i+1][k][1][2][0][1]+P1[j-1][k][2][1][0][1]+P1[j][k][2][0][0][1]+V1[j-2][k][2][2][0][1]-V1[i+1][k][2][2][0][1];
t2+=P2[i][k][0][2][0][1]+P2[i+1][k][1][2][0][1]+P2[j-1][k][2][1][0][1]+P2[j][k][2][0][0][1]+V2[j-2][k][2][2][0][1]-V2[i+1][k][2][2][0][1];
t1+=P1[i][k+1][0][2][1][0]+P1[i+1][k+1][1][2][1][0]+P1[j-1][k+1][2][1][1][0]+P1[j][k+1][2][0][1][0]+V1[j-2][k+1][2][2][1][0]-V1[i+1][k+1][2][2][1][0];
t2+=P2[i][k+1][0][2][1][0]+P2[i+1][k+1][1][2][1][0]+P2[j-1][k+1][2][1][1][0]+P2[j][k+1][2][0][1][0]+V2[j-2][k+1][2][2][1][0]-V2[i+1][k+1][2][2][1][0];
if(t1==1 && t2==1) ans++;
}
for(int k=1; k<=M-2; k++)
{
int t1=0, t2=0;
t1+=P1[i][k][0][2][0][2]+P1[i+1][k][1][2][0][2]+P1[j-1][k][2][1][0][2]+P1[j][k][2][0][0][2]+V1[j-2][k][2][2][0][2]-V1[i+1][k][2][2][0][2];
t2+=P2[i][k][0][2][0][2]+P2[i+1][k][1][2][0][2]+P2[j-1][k][2][1][0][2]+P2[j][k][2][0][0][2]+V2[j-2][k][2][2][0][2]-V2[i+1][k][2][2][0][2];
t1+=P1[i][k+1][0][2][1][1]+P1[i+1][k+1][1][2][1][1]+P1[j-1][k+1][2][1][1][1]+P1[j][k+1][2][0][1][1]+V1[j-2][k+1][2][2][1][1]-V1[i+1][k+1][2][2][1][1];
t2+=P2[i][k+1][0][2][1][1]+P2[i+1][k+1][1][2][1][1]+P2[j-1][k+1][2][1][1][1]+P2[j][k+1][2][0][1][1]+V2[j-2][k+1][2][2][1][1]-V2[i+1][k+1][2][2][1][1];
t1+=P1[i][k+2][0][2][2][0]+P1[i+1][k+2][1][2][2][0]+P1[j-1][k+2][2][1][2][0]+P1[j][k+2][2][0][2][0]+V1[j-2][k+2][2][2][2][0]-V1[i+1][k+2][2][2][2][0];
t2+=P2[i][k+2][0][2][2][0]+P2[i+1][k+2][1][2][2][0]+P2[j-1][k+2][2][1][2][0]+P2[j][k+2][2][0][2][0]+V2[j-2][k+2][2][2][2][0]-V2[i+1][k+2][2][2][2][0];
if(t1==1 && t2==1) ans++;
}
for(int k=1; k<=M; k++)
{
if(k+1<=M) B11[k]+=P1[i][k][0][2][0][2]+P1[i][k+1][0][2][1][2]-H1[i][k+1][0][2][2][2];
if(k-2>=0) B12[k]+=P1[i][k][0][2][2][0]+P1[i][k-1][0][2][2][1]+H1[i][k-2][0][2][2][2];
if(k+1<=M) B21[k]+=P2[i][k][0][2][0][2]+P2[i][k+1][0][2][1][2]-H2[i][k+1][0][2][2][2];
if(k-2>=0) B22[k]+=P2[i][k][0][2][2][0]+P2[i][k-1][0][2][2][1]+H2[i][k-2][0][2][2][2];
if(k+1<=M) B11[k]+=P1[i+1][k][1][2][0][2]+P1[i+1][k+1][1][2][1][2]-H1[i+1][k+1][1][2][2][2];
if(k-2>=0) B12[k]+=P1[i+1][k][1][2][2][0]+P1[i+1][k-1][1][2][2][1]+H1[i+1][k-2][1][2][2][2];
if(k+1<=M) B21[k]+=P2[i+1][k][1][2][0][2]+P2[i+1][k+1][1][2][1][2]-H2[i+1][k+1][1][2][2][2];
if(k-2>=0) B22[k]+=P2[i+1][k][1][2][2][0]+P2[i+1][k-1][1][2][2][1]+H2[i+1][k-2][1][2][2][2];
if(k+1<=M) B11[k]+=P1[j][k][2][0][0][2]+P1[j][k+1][2][0][1][2]-H1[j][k+1][2][0][2][2];
if(k-2>=0) B12[k]+=P1[j][k][2][0][2][0]+P1[j][k-1][2][0][2][1]+H1[j][k-2][2][0][2][2];
if(k+1<=M) B21[k]+=P2[j][k][2][0][0][2]+P2[j][k+1][2][0][1][2]-H2[j][k+1][2][0][2][2];
if(k-2>=0) B22[k]+=P2[j][k][2][0][2][0]+P2[j][k-1][2][0][2][1]+H2[j][k-2][2][0][2][2];
if(k+1<=M) B11[k]+=P1[j-1][k][2][1][0][2]+P1[j-1][k+1][2][1][1][2]-H1[j-1][k+1][2][1][2][2];
if(k-2>=0) B12[k]+=P1[j-1][k][2][1][2][0]+P1[j-1][k-1][2][1][2][1]+H1[j-1][k-2][2][1][2][2];
if(k+1<=M) B21[k]+=P2[j-1][k][2][1][0][2]+P2[j-1][k+1][2][1][1][2]-H2[j-1][k+1][2][1][2][2];
if(k-2>=0) B22[k]+=P2[j-1][k][2][1][2][0]+P2[j-1][k-1][2][1][2][1]+H2[j-1][k-2][2][1][2][2];
if(k+1<=M) B11[k]+=(V1[j-2][k][2][2][0][2]-V1[i+1][k][2][2][0][2])+(V1[j-2][k+1][2][2][1][2]-V1[i+1][k+1][2][2][1][2])-(S1[j-2][k+1][2][2][2][2]-S1[i+1][k+1][2][2][2][2]);
if(k-2>=0) B12[k]+=(V1[j-2][k][2][2][2][0]-V1[i+1][k][2][2][2][0])+(V1[j-2][k-1][2][2][2][1]-V1[i+1][k-1][2][2][2][1])-(S1[j-2][k-2][2][2][2][2]-S1[i+1][k-2][2][2][2][2]);
if(k+1<=M) B21[k]+=(V2[j-2][k][2][2][0][2]-V2[i+1][k][2][2][0][2])+(V2[j-2][k+1][2][2][1][2]-V2[i+1][k+1][2][2][1][2])-(S2[j-2][k+1][2][2][2][2]-S2[i+1][k+1][2][2][2][2]);
if(k-2>=0) B22[k]+=(V2[j-2][k][2][2][2][0]-V2[i+1][k][2][2][2][0])+(V2[j-2][k-1][2][2][2][1]-V2[i+1][k-1][2][2][2][1])-(S2[j-2][k-2][2][2][2][2]-S2[i+1][k-2][2][2][2][2]);
}
solve();
}
}
printf("%lld\n", ans);
}
Compilation message
Main.cpp: In function 'int naive(int, int, int, int)':
Main.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=1; i<V.size(); i++) if(abs(V[i].second.first-V[i-1].second.first)+abs(V[i].second.second-V[i-1].second.second)!=1) return false;
| ~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:67:62: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%d", &A[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:73:62: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | for(int i=1; i<=M; i++) for(int j=1; j<=N; j++) scanf("%d", &A[j][i]);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
267 ms |
397156 KB |
Output is correct |
| 3 |
Correct |
269 ms |
390268 KB |
Output is correct |
| 4 |
Correct |
257 ms |
397056 KB |
Output is correct |
| 5 |
Correct |
264 ms |
397196 KB |
Output is correct |
| 6 |
Correct |
276 ms |
397140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
