#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define pii pair < int, int >
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
using namespace std;
const ll inf = (ll) 1e11;
const vector < ll > nul;
int h, w;
vector < vector < ll > > mat;
vector < vector < ll > > prefsum[16];// 1 = x + 1, 2 = y + 1, 4 = x - 1, 8 = y - 1
pii dir[4] = {mp(0, 1), mp(1, 0), mp(0, -1), mp(-1, 0)};
int l2[16] = {0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3};
unordered_map < ll, ll > rep;
bool inbounds( int y, int x ) {return (y >= 0 && y < h && x >= 0 && x < w);}
void flipmat( void ) {
vector < vector < ll > > newmat;
for(int i = 0; i < w; i++) {
newmat.pb(nul);
for(int j = 0; j < h; j++) {
newmat[i].pb(mat[j][i]);
}
}
mat = newmat;
swap(h, w);
return;
}
ll rec( int k, int y1, int x1, int y2, int x2 ) {
return prefsum[k][y1][x1] - prefsum[k][y2][x1] - prefsum[k][y1][x2] + prefsum[k][y2][x2];
}
void task( void ) {
cin >> h >> w;
for(int i = 0; i < h; i++) {
mat.pb(nul);
for(int j = 0; j < w; j++) {
mat[i].pb(0);
cin >> mat[i][j];
}
}
if(h > w) flipmat();
int curbit;
int prevval;
//mark sus
for(int i = 0; i < 16; i++) {
prefsum[i].pb(nul);
for(int j = 0; j < w + 1; j++) prefsum[i][0].pb(0);
curbit = l2[i & -i];
for(int j = 1; j < h + 1; j++) {
prefsum[i].pb(nul);
prefsum[i][j].pb(0);
for(int z = 1; z < w + 1; z++) {
prefsum[i][j].pb(mat[j - 1][z - 1]);
}
}
if(i != 0) {
prevval = i - (i&-i);
for(int j = 1; j < h + 1; j++) {
for(int z = 1; z < w + 1; z++) {
prefsum[i][j][z] = prefsum[prevval][j][z];
if(inbounds(j + dir[curbit].F - 1, z + dir[curbit].S - 1) && mat[j + dir[curbit].F - 1][z + dir[curbit].S - 1] < mat[j - 1][z - 1])
prefsum[i][j][z] = min(prefsum[prevval][j][z], mat[j - 1][z - 1] - mat[j + dir[curbit].F - 1][z + dir[curbit].S - 1]);
}
}
}
}
//mark the biggest
bool biggest;
for(int i = 0; i < 16; i++) {
for(int j = 0; j < h; j++) {
for(int z = 0; z < w; z++) {
biggest = 1;
for(int k = 0; k < 4; k++) {
if(inbounds(j + dir[k].F, z + dir[k].S) && ((1<<k) & i)
&& mat[j + dir[k].F][z + dir[k].S] > mat[j][z]) biggest = 0;
}
if(biggest) prefsum[i][j + 1][z + 1] += inf - mat[j][z];
}
}
}
//make sums
for(int i = 0; i < 16; i++) {
for(int j = 1; j < h + 1; j++) {
for(int z = 1; z < w + 1; z++) {
prefsum[i][j][z] += prefsum[i][j - 1][z] + prefsum[i][j][z - 1] - prefsum[i][j - 1][z - 1];
}
}
}
ll cur = 0;
ll sol = 0;
for(int i = 0; i < h; i++) {
for(int j = i; j < h; j++) {
cur = 0;
rep.clear();
for(int z = 0; z < w; z++) {
if(j - i > 0) {
if(rec(2, i, z, i + 1, z + 1) + rec(8, j, z, j + 1, z + 1) + rec(10, i + 1, z, j, z + 1) == inf) sol++;
sol += rep[inf - rec(6, i, z, i + 1, z + 1) - rec(12, j, z, j + 1, z + 1) - rec(14, i + 1, z, j, z + 1) - cur];
cur += rec(7, i, z, i + 1, z + 1) + rec(13, j, z, j + 1, z + 1) + rec(15, i + 1, z, j, z + 1);
rep[rec(3, i, z, i + 1, z + 1) + rec(9, j, z, j + 1, z + 1) + rec(11, i + 1, z, j, z + 1) - cur]++;
}
else {
sol++;
sol += rep[inf - rec(4, i, z, i + 1, z + 1) - cur];
cur += rec(5, i, z, i + 1, z + 1);
rep[rec(1, i, z, i + 1, z + 1) - cur]++;
}
}
}
}
cout << sol << "\n";
return;
}
int main( void ) {
FIO;
task();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |