#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Sit {
int nbMax, nbMin, col;
};
const int M = 5e4 + 42, N = 5 * M, K = 230, INF = 1e18 + 42;
Sit l[M], r[M];
int n, m, val[N];
vector<Sit> deb[K][K], fin[K][K];
int dl[] = {0, 0, 1, -1},
dc[] = {1, -1, 0, 0};
inline int getId(int i, int j) {
return (i + 2) * (m + 4) + (j + 2);
}
struct SDD {
bool isMin[N];
int value[N], nbPre[N], nbMin[M], nbSup[M], nbMinCol[M], nbPreCol[M];
void init() {
for(int i = 0; i < N; i++)
value[i] = INF;
}
void getNext(int i, int j, int cancel) {
if(value[getId(i, j)] == INF)
return;
int id = -1;
for(int k = 0; k < 4; k++) {
int id2 = getId(i + dl[k], j + dc[k]);
if(value[getId(i, j)] > value[id2]) {
if(id == -1 || value[id2] > value[id])
id = id2;
}
}
if(id == -1) {
if(isMin[getId(i, j)])
nbMinCol[j]--;
if(cancel != -1)
nbMinCol[j]++;
isMin[getId(i, j)] = (cancel != -1);
} else {
int iCol = (id % (m+4)) - 2;
if(nbPre[id] > 1)
nbSup[iCol]--;
nbPre[id] += cancel;
if(nbPre[id] > 1)
nbSup[iCol]++;
nbPreCol[iCol] += cancel;
}
}
void update(int i, int j, int cancel) {
getNext(i, j, cancel);
for(int k = 0; k < 4; k++)
getNext(i + dl[k], j + dc[k], cancel);
}
void change(int i, int j, int newVal) {
update(i, j, -1);
value[getId(i, j)] = newVal;
update(i, j, 1);
}
};
SDD sdd;
int ans = 0;
void count3() {
for(int width = 1; width < 4; width++) {
for(int i = 0; i <= m-width; i++) {
for(int j = 0; j < n; j++) {
for(int k = j; k < n; k++) {
for(int l = i; l < i+width; l++)
sdd.change(k, l, val[getId(k, l)]);
int nbPre = 0, nbMin = 0, nbSup = 0;
for(int l = i; l < i+width; l++)
nbPre += sdd.nbPreCol[l],
nbMin += sdd.nbMinCol[l],
nbSup += sdd.nbSup[l];
if(nbPre == width * (k - j + 1) - 1 && nbMin == 1 && nbSup == 0) {
ans++;
}
}
for(int k = j; k < n; k++)
for(int l = i; l < i+width; l++)
sdd.change(k, l, INF);
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
sdd.init();
cin >> n >> m;
int n2 = n, m2 = m;
if(n > m)
swap(n, m);
for(int i = 0; i < n2; i++)
for(int j = 0; j < m2; j++)
if(n2 <= m2)
cin >> val[getId(i, j)];
else
cin >> val[getId(j, i)];
count3();
for(int i = 0; i <= m-4; i++) {
for(int j = 0; j < n; j++) {
for(int k = j; k < n; k++) {
for(int l = i; l < i+4; l++)
sdd.change(k, l, val[getId(k, l)]);
if(sdd.nbSup[i] == 0 && sdd.nbSup[i+1] == 0 && sdd.nbMinCol[i] + sdd.nbMinCol[i+1] < 2 && sdd.nbPreCol[i] + sdd.nbPreCol[i+1] >= 2*(k-j)+1) {
deb[j][k].push_back({2*(k-j+1) - sdd.nbPreCol[i] - sdd.nbPreCol[i+1], sdd.nbMinCol[i] + sdd.nbMinCol[i+1], i+2});
}
if(sdd.nbSup[i+2] == 0 && sdd.nbSup[i+3] == 0 && sdd.nbMinCol[i+2] + sdd.nbMinCol[i+3] < 2 && sdd.nbPreCol[i+2] + sdd.nbPreCol[i+3] >= 2*(k-j)+1) {
fin[j][k].push_back({2*(k-j+1) - sdd.nbPreCol[i+2] - sdd.nbPreCol[i+3], sdd.nbMinCol[i+2] + sdd.nbMinCol[i+3], i+2});
}
}
for(int k = j; k < n; k++)
for(int l = i; l < i+4; l++)
sdd.change(k, l, INF);
}
}
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
for(int k = 0; k < m; k++)
sdd.change(j, k, val[getId(j, k)]);
for(int k = 0; k < m; k++) {
l[k].col = r[k].col = -1;
l[k].nbMin = r[k].nbMin = l[k].nbMax = r[k].nbMax = 0;
}
for(Sit sit : deb[i][j]) {
l[sit.col].col = 0;
l[sit.col].nbMax = sit.nbMax;
l[sit.col].nbMin = sit.nbMin;
}
for(Sit sit : fin[i][j]) {
r[sit.col].col = 0;
r[sit.col].nbMax = sit.nbMax;
r[sit.col].nbMin = sit.nbMin;
}
for(int nbmin : {0, 1})
for(int nbmax : {0, 1}) {
int nbMin = nbmin, nbMax = nbmax,
right = 1, nbType[2][2] = {{0, 0}, {0, 0}};
for(int left = 2; left < m-1; left++) {
if(right < left) {
right++;
if(r[right].col != -1)
nbType[r[right].nbMin][r[right].nbMax]++;
}
while(right < m-2 && sdd.nbSup[right] == 0 && (nbMin >= sdd.nbMinCol[right] && nbMax >= (j-i+1) - sdd.nbPreCol[right])) {
nbMin -= sdd.nbMinCol[right],
nbMax -= (j-i+1) - sdd.nbPreCol[right];
right++;
if(r[right].col != -1)
nbType[r[right].nbMin][r[right].nbMax]++;
}
if(nbMin == 0 && nbMax == 0 && nbmin + l[left].nbMin <= 1 && nbmax + l[left].nbMax <= 1) {
ans += nbType[1 - nbmin - l[left].nbMin][1 - nbmax - l[left].nbMax];
}
if(r[left].col != -1)
nbType[r[left].nbMin][r[left].nbMax]--;
if(left < right) {
nbMin += sdd.nbMinCol[left],
nbMax += (j-i+1) - sdd.nbPreCol[left];
}
}
}
}
for(int j = i; j < n; j++)
for(int k = 0; k < m; k++)
sdd.change(j, k, INF);
}
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4692 KB |
Output is correct |
| 2 |
Correct |
46 ms |
11568 KB |
Output is correct |
| 3 |
Correct |
53 ms |
10716 KB |
Output is correct |
| 4 |
Correct |
48 ms |
11552 KB |
Output is correct |
| 5 |
Correct |
47 ms |
11660 KB |
Output is correct |
| 6 |
Correct |
50 ms |
11264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
