This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
#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 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;
debug(bu, bd, bl, br, i, j);
// 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;
debug(ni, nj, to_num);
}
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 ub = 0; ub < H; ++ub) {
int cur = 0, val;
for (int db = ub; db < H; ++db) {
if (db - ub + 1 == 1) val = get_sum(0, ub, lb, rb);
if (db - ub + 1 == 2) val = get_sum(1, ub, lb, rb);
if (db - ub + 1 == 3) val = get_sum(2, ub, lb, rb);
if (db - ub + 1 == 4) val = get_sum(3, ub, lb, rb) + get_sum(4, ub + 2, lb, rb);
if (db - ub + 1 >= 5) {
cur += get_sum(5, db - 2, lb, rb);
val = get_sum(3, ub, lb, rb) + cur + get_sum(4, db - 1, lb, rb);
}
ans += (val == 1);
debug(lb, rb, ub, db, val);
}
}
cout << ans << '\n';
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... |