#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("avx2")
using namespace std;
const int N = 15013;
const int SQ = 240;
int a[200013];
int b[200013];
bool f[200013];
int s[200013];
int h, w;
int id(int i, int j){
return i * (w + 1) + j;
}
int id2(int i, int j){
return j * (h + 1) + i;
}
struct Range{
short x1, x2, y1, y2; // 1D; [x1, x2] x [y1, y2]
};
vector<Range> vrs[SQ][SQ];
int qry(int x1, int x2, int y1, int y2){
return s[id(x2 + 1, y2 + 1)] + s[id(x1, y1)] - s[id(x2 + 1, y1)] - s[id(x1, y2 + 1)];
}
struct PartialSum2D{
short a[N][N] = {0}, ps[N][N] = {0};
void clear(int n){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
a[i][j] = ps[i][j] = 0;
}
}
}
void upd(int x1, int x2, int y1, int y2, int v){
a[x2 + 1][y2 + 1] += v;
a[x1][y2 + 1] -= v;
a[x2 + 1][y1] -= v;
a[x1][y1] += v;
}
void run(int n){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + a[i - 1][j - 1];
}
}
}
int qry(int x, int y){
return ps[x + 1][y + 1];
}
} ps;
int g(vector<Range>& vr, int h){
ps.clear(w);
for(auto r : vr){
ps.upd(r.x1, r.x2, r.y1, r.y2, 1);
}
ps.run(w);
int ans = 0;
for(int i = 0; i < w; i++){
for(int j = i; j < w; j++){
ans += ps.qry(i, j) == h * (j - i + 1) - 1;
}
}
return ans;
}
int32_t main(){
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> h >> w;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
cin >> a[id(i, j)];
}
}
if(h > w){
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
b[id2(i, j)] = a[id(i, j)];
}
}
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
a[id2(i, j)] = b[id2(i, j)];
}
}
swap(w, h);
}
{
set<int> S; map<int, int> M;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
S.insert(a[id(i, j)]);
}
}
int idx = 0;
for(auto j : S){
M[j] = idx++;
}
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
a[id(i, j)] = M[a[id(i, j)]];
}
}
}
int ans = 0;
for(int i = 0; i < h; i++){
for(int j = 0; j < w - 1; j++){
int v1 = a[id(i, j)], v2 = a[id(i, j + 1)];
if(v1 > v2) swap(v1, v2);
for(int x = 0; x < h; x++){
for(int y = 0; y < w; y++){
f[id(x, y)] = a[id(x, y)] > v1 && a[id(x, y)] < v2;
}
}
for(int x = 0; x < h; x++){
for(int y = 0; y < w; y++){
s[id(x + 1, y + 1)] = s[id(x + 1, y)] + s[id(x, y + 1)] - s[id(x, y)] + f[id(x, y)];
}
}
int x1 = i, x2 = i, y1 = j, y2 = j + 1;
for(int x3 = 0; x3 <= x1; x3++){
int y3 = 0, y4 = w - 1;
for(int x4 = x2; x4 < h; x4++){
if(qry(x3, x4, y1, y2)) continue;
while(qry(x3, x4, y3, y1)) y3++;
while(qry(x3, x4, y2, y4)) y4--;
vrs[x3][x4].emplace_back({y3, y1, y2, y4});
}
}
}
}
for(int i = 0; i < h - 1; i++){
for(int j = 0; j < w; j++){
int v1 = a[id(i, j)], v2 = a[id(i + 1, j)];
if(v1 > v2) swap(v1, v2);
for(int x = 0; x < h; x++){
for(int y = 0; y < w; y++){
f[id(x, y)] = a[id(x, y)] > v1 && a[id(x, y)] < v2;
}
}
for(int x = 0; x < h; x++){
for(int y = 0; y < w; y++){
s[id(x + 1, y + 1)] = s[id(x + 1, y)] + s[id(x, y + 1)] - s[id(x, y)] + f[id(x, y)];
}
}
int x1 = i, x2 = i + 1, y1 = j, y2 = j;
for(int x3 = 0; x3 <= x1; x3++){
int y3 = 0, y4 = w - 1;
for(int x4 = x2; x4 < h; x4++){
if(qry(x3, x4, y1, y2)) continue;
while(qry(x3, x4, y3, y1)) y3++;
while(qry(x3, x4, y2, y4)) y4--;
vrs[x3][x4].emplace_back({y3, y1, y2, y4});
}
}
}
}
for(int x1 = 0; x1 < h; x1++){
for(int x2 = x1; x2 < h; x2++){
ans += g(vrs[x1][x2], x2 - x1 + 1);
}
}
cout << ans << endl;
}
Compilation message
Main.cpp:4:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
4 | #pragma GCC optimize("avx2")
| ^
Main.cpp:14:20: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
14 | int id(int i, int j){
| ^
Main.cpp:17:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
17 | int id2(int i, int j){
| ^
Main.cpp:26:39: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
26 | int qry(int x1, int x2, int y1, int y2){
| ^
Main.cpp:33:18: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
33 | void clear(int n){
| ^
Main.cpp:40:48: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
40 | void upd(int x1, int x2, int y1, int y2, int v){
| ^
Main.cpp:46:16: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
46 | void run(int n){
| ^
Main.cpp:53:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
53 | int qry(int x, int y){
| ^
Main.cpp:58:31: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
58 | int g(vector<Range>& vr, int h){
| ^
Main.cpp:73:14: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
73 | int32_t main(){
| ^
Main.cpp: In function 'int32_t main()':
Main.cpp:136:47: error: no matching function for call to 'std::vector<Range>::emplace_back(<brace-enclosed initializer list>)'
136 | vrs[x3][x4].emplace_back({y3, y1, y2, y4});
| ^
In file included from /usr/include/c++/10/vector:72,
from /usr/include/c++/10/queue:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/vector.tcc:109:7: note: candidate: 'void std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {}; _Tp = Range; _Alloc = std::allocator<Range>]'
109 | vector<_Tp, _Alloc>::
| ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:109:7: note: candidate expects 0 arguments, 1 provided
Main.cpp:163:47: error: no matching function for call to 'std::vector<Range>::emplace_back(<brace-enclosed initializer list>)'
163 | vrs[x3][x4].emplace_back({y3, y1, y2, y4});
| ^
In file included from /usr/include/c++/10/vector:72,
from /usr/include/c++/10/queue:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from Main.cpp:1:
/usr/include/c++/10/bits/vector.tcc:109:7: note: candidate: 'void std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {}; _Tp = Range; _Alloc = std::allocator<Range>]'
109 | vector<_Tp, _Alloc>::
| ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:109:7: note: candidate expects 0 arguments, 1 provided
