#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 700 + 4;
int l[N][N][N];
int r[N][N][N];
int u[N][N][N];
int d[N][N][N];
int get_l(int k, int i, int j, int ii, int jj) {return l[k][ii+1][jj+1] - l[k][ii+1][j] - l[k][i][jj+1] + l[k][i][j];}
int get_r(int k, int i, int j, int ii, int jj) {return r[k][ii+1][jj+1] - r[k][ii+1][j] - r[k][i][jj+1] + r[k][i][j];}
int get_u(int k, int i, int j, int ii, int jj) {return u[k][ii+1][jj+1] - u[k][ii+1][j] - u[k][i][jj+1] + u[k][i][j];}
int get_d(int k, int i, int j, int ii, int jj) {return d[k][ii+1][jj+1] - d[k][ii+1][j] - d[k][i][jj+1] + d[k][i][j];}
long long count_rectangles(std::vector<std::vector<int>> a) {
int n = a.size();
int m = a[0].size();
for (int i=0; i<n; i++) for (int j=0; j<m; j++) {
for (int k=j-1; k>=0; k--) if (a[i][j]<a[i][k]) l[k+1][i+1][j+1]=1;
for (int k=j+1; k<m ; k++) if (a[i][j]<a[i][k]) r[k-1][i+1][j+1]=1;
for (int k=i-1; k>=0; k--) if (a[i][j]<a[k][j]) u[k+1][i+1][j+1]=1;
for (int k=i+1; k<n ; k++) if (a[i][j]<a[k][j]) d[k-1][i+1][j+1]=1;
}
// cout << r[1][1][1] << ' ' << r[1][1][2] << '\n';
// cout << r[1][2][1] << ' ' << r[1][2][2] << '\n';
for (int k=0; k<m; k++) for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) {
l[k][i][j] += l[k][i-1][j] + l[k][i][j-1] - l[k][i-1][j-1];
r[k][i][j] += r[k][i-1][j] + r[k][i][j-1] - r[k][i-1][j-1];
}
for (int k=0; k<n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) {
u[k][i][j] += u[k][i-1][j] + u[k][i][j-1] - u[k][i-1][j-1];
d[k][i][j] += d[k][i-1][j] + d[k][i][j-1] - d[k][i-1][j-1];
}
// cout << r[1][1][1] << ' ' << r[1][1][2] << '\n';
// cout << r[1][2][1] << ' ' << r[1][2][2] << '\n';
int ans=0;
for (int i=1; i+1<n; i++) for (int j=1; j+1<m; j++) {
for (int ii=i; ii+1<n; ii++) for (int jj=j; jj+1<m; jj++) {
int s = (ii-i+1) * (jj-j+1);
// if (i==j && j==ii && ii==jj && i==1) cout << (get_l(j,i,j,ii,jj)==s) << (get_r(jj,i,j,ii,jj)==s) << (get_u(i,i,j,ii,jj)==s) << (get_d(ii,i,j,ii,jj)==s) << '\n';
ans += get_l(j,i,j,ii,jj)==s && get_r(jj,i,j,ii,jj)==s && get_u(i,i,j,ii,jj)==s && get_d(ii,i,j,ii,jj)==s;
}
}
return ans;
}
Compilation message (stderr)
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(vterminate.o): in function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1e): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x2b): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1c): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x60): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x67): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x72): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x87): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x92): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xa7): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xb2): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xc1): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/11/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xd4): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1c6): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x260): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2e2): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x353): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x541): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5e5): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x670): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x6e9): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status
