#include <bits/stdc++.h>
#define int short
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{
int 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 BIT{
int bit[N][N] = {0};
void clear(int n){
n += 10;
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
bit[i][j] = 0;
}
}
}
void upd(int x, int y, int v){
x += 2; y += 2;
for(int i = x; i < w + 10; i += i & -i){
for(int j = y; j < w + 10; j += j & -j){
bit[i][j] += v;
}
}
}
void upd(int x1, int x2, int y1, int y2, int v){
upd(x2 + 1, y2 + 1, v);
upd(x1, y2 + 1, -v);
upd(x2 + 1, y1, -v);
upd(x1, y1, v);
}
int qry(int x, int y){
x += 2; y += 2;
int ret = 0;
for(int i = x; i; i -= i & -i){
for(int j = y; j; j -= j & -j){
ret += bit[i][j];
}
}
return ret;
}
int qry(int x1, int x2, int y1, int y2){
return qry(x2, y2) - qry(x2, y1 - 1) - qry(x1 - 1, y2) + qry(x1 - 1, y1 - 1);
}
} bit;
int g(vector<Range> vr, int h){
bit.clear(w);
for(auto r : vr){
bit.upd(r.x1, r.x2, r.y1, r.y2, 1);
}
int ans = 0;
for(int i = 0; i < w; i++){
for(int j = i; j < w; j++){
ans += bit.qry(i, j) == h * (j - i + 1) - 1;
}
}
return ans;
}
int32_t main(){
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++){
for(int x4 = x2; x4 < h; x4++){
if(qry(x3, x4, y1, y2)) continue;
int y3 = INT16_MAX, y4 = INT16_MIN;
{
int l = 0, r = y1;
while(l != r){
int mid = (l + r) / 2;
if(qry(x3, x4, mid, y1)){
l = mid + 1;
}else{
r = mid;
}
}
y3 = l;
}
{
int l = y2, r = w - 1;
while(l != r){
int mid = (l + r + 1) / 2;
if(qry(x3, x4, y2, mid)){
r = mid - 1;
}else{
l = mid;
}
}
y4 = l;
}
vrs[x3][x4].push_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++){
for(int x4 = x2; x4 < h; x4++){
if(qry(x3, x4, y1, y2)) continue;
int y3 = INT16_MAX, y4 = INT16_MIN;
{
int l = 0, r = y1;
while(l != r){
int mid = (l + r) / 2;
if(qry(x3, x4, mid, y1)){
l = mid + 1;
}else{
r = mid;
}
}
y3 = l;
}
{
int l = y2, r = w - 1;
while(l != r){
int mid = (l + r + 1) / 2;
if(qry(x3, x4, y2, mid)){
r = mid - 1;
}else{
l = mid;
}
}
y4 = l;
}
vrs[x3][x4].push_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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1620 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1748 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
