/*
#include <bits/stdc++.h>
using namespace std;
*/
// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#define debug(...) ((void)0)
#endif
// d, u, r, l
const int di[4] = {1, -1, 0, 0};
const int dj[4] = {0, 0, 1, -1};
const int kN = 51215;
int H, W, A[kN], AT[kN];
int B[9][9][kN], C[9][6][kN], D[6][6][kN], S[6][kN];
int PS5[kN], SA[kN], SB[kN], cnt[kN];
int get_sum(int th, int i, int lb, int rb) {
if (rb - lb + 1 == 1) return D[th][0][i * W + lb];
if (rb - lb + 1 == 2) return D[th][1][i * W + lb];
if (rb - lb + 1 == 3) return D[th][2][i * W + lb];
if (rb - lb + 1 == 4) return D[th][3][i * W + lb] + D[th][4][i * W + lb + 2];
return D[th][3][i * W + lb] +
(S[th][i * W + rb - 1] - S[th][i * W + lb + 2]) +
D[th][4][i * W + rb - 1];
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> H >> W;
for (int i = 0; i < H * W; ++i)
cin >> A[i];
if (H < W) {
for (int i = 0; i < H * W; ++i)
AT[(i % W) * H + (i / W)] = A[i];
for (int i = 0; i < H * W; ++i)
A[i] = AT[i];
swap(H, W);
}
// B[th][tw][i]: in degree of cell i when U-D side type th, L-R type tw
// 0: - -[x]- - 1: - -[x -]- 2: - -[x - -|
// 3: -[- x]- - 4: -[- x -]- 5: -[- x - -|
// 6: |- - x]- - 7: |- - x -]- 8: |- - x - -|
// [: Edge |: not necessary an edge
for (int th = 0; th < 9; ++th)
for (int tw = 0; tw < 9; ++tw)
for (int i = 0; i < H; ++i)
for (int j = 0; j < W; ++j) {
int bu = i - th / 3, bd = i + th % 3;
int bl = j - tw / 3, br = j + tw % 3;
if (bu < 0 or bd >= H or bl < 0 or br >= W)
continue;
// iterate neighbor
int indeg = 0;
for (int d = 0; d < 4; ++d) {
int ni = i + di[d], nj = j + dj[d];
if (ni < bu or ni > bd or nj < bl or nj > br or A[i * W + j] > A[ni * W + nj])
continue;
// iterate neighbor's neighbor
int to_num = A[i * W + j];
for (int dn = 0; dn < 4; ++dn) {
int mi = ni + di[dn], mj = nj + dj[dn];
if (mi < bu or mi > bd or mj < bl or mj > br or A[mi * W + mj] > A[ni * W + nj])
continue;
to_num = max(to_num, A[mi * W + mj]);
}
if (to_num == A[i * W + j])
++indeg;
}
B[th][tw][i * W + j] = (indeg == 0);
}
// Gather the values of cells at the edges.
// C[th][tw][i]: in degree of cell i when U-D side type th, L-R type tw
// 0: [x] 1: [x -] + [- x] 2: [x - -] + [- x -] + [- - x]
// 3: [x - - -| + [- x - -| 4: |- - x -] + |- - - x]
// 5: |- - x - -|
// The left bound of a type is the same.
// D goes the same way.
for (int th = 0; th < 9; ++th)
for (int i = 0; i < H * W; ++i) {
C[th][0][i] = B[th][0][i];
C[th][1][i] = B[th][1][i] + B[th][3][i + 1];
C[th][2][i] = B[th][2][i] + B[th][4][i + 1] + B[th][6][i + 2];
C[th][3][i] = B[th][2][i] + B[th][5][i + 1];
C[th][4][i] = B[th][7][i] + B[th][6][i + 1];
C[th][5][i] = B[th][8][i];
}
for (int tw = 0; tw < 6; ++tw)
for (int i = 0; i < H * W; ++i) {
D[0][tw][i] = C[0][tw][i];
D[1][tw][i] = C[1][tw][i] + C[3][tw][i + W];
D[2][tw][i] = C[2][tw][i] + C[4][tw][i + W] + C[6][tw][i + 2 * W];
D[3][tw][i] = C[2][tw][i] + C[5][tw][i + W];
D[4][tw][i] = C[7][tw][i] + C[6][tw][i + W];
D[5][tw][i] = C[8][tw][i];
}
// Calculate prefix sum
// S[th][i]: prefix sum when U-D side type th, L-R must be type 5 (inner ones)
for (int th = 0; th < 6; ++th)
for (int i = 0; i < H * W; ++i)
S[th][i + 1] = S[th][i] + D[th][5][i];
int ans = 0;
for (int lb = 0; lb < W; ++lb)
for (int rb = lb; rb < W; ++rb) {
for (int i = 0; i < H; ++i) {
PS5[i] = get_sum(5, i, lb, rb) + (i > 0 ? PS5[i - 1] : 0);
SA[i] = PS5[i] - (i >= 1 ? get_sum(3, i - 1, lb, rb) : 0);
SB[i] = (i >= 2 ? PS5[i - 2] : 0) + (i >= 1 ? get_sum(4, i - 1, lb, rb) : 0);
}
for (int i = 0; i < H; ++i) {
for (int d = 0; d < 3 and i - d >= 0; ++d)
ans += (get_sum(d, i - d, lb, rb) == 1);
if (i < 3) continue;
if (SA[i - 2] >= 0) cnt[SA[i - 2]]++;
ans += (SB[i] >= 1 ? cnt[SB[i] - 1] : 0);
}
for (int i = 0; i + 2 < H; ++i)
if (SA[i] >= 0) cnt[SA[i]] = 0;
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
716 KB |
Output is correct |
| 2 |
Incorrect |
38 ms |
22696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1100 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
