#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int int64_t
#define double long double
using pii = pair<int, int>;
template <typename T>
using Prior = std::priority_queue<T>;
template <typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;
#define X first
#define Y second
#define ee emplace
#define eb emplace_back
#define ef push_front
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
#ifdef local
#define fastIO() void()
#define debug(...) \
cerr << "\u001b[33m" << "At func " << __FUNCTION__ << ", line " << __LINE__ << ": ",\
cerr << "(" << #__VA_ARGS__ << ") = ",\
_do(__VA_ARGS__),\
cerr << "\u001b[0m"
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif
template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}
const int dx[] = {1, 0,-1, 0};
const int dy[] = {0, 1, 0,-1};
void solve() {
int H, W; cin >> H >> W;
if (H == 1) {
vector<int> board(W);
for (int &x : board) cin >> x;
int ans = W;
for (int i = 1, flag = 0, len = 0; i < W; ++i) {
if (flag == 0 and board[i] > board[i-1]) flag = 1, len = 0;
else if (flag == 1 and board[i] < board[i-1]) flag = 0, len = 0;
ans += ++len;
}
return cout << ans << "\n";
}
vector<vector<int>> board(H+2, vector<int>(W+2, 0));
for (int i = 1; i <= H; ++i) for (int j = 1; j <= W; ++j) cin >> board[i][j];
auto valid = [&](int x, int y) -> bool {
return 0 <= x and x <= H+1 and 0 <= y and y <= W+1;
};
auto check = [&](int nx, int ny, int gx, int gy, int l, int r, int d, int u) -> bool {
/// x-l, x+r, y-d, y+u ///
if (!(nx-l <= gx and gx <= nx+r and ny-d <= gy and gy <= ny+u)) return false;
int mx_nei = 0, mx_dir = -1;
for (int _ : {0, 1, 2, 3}) {
int tx = gx + dx[_], ty = gy + dy[_];
if (!(nx-l <= tx and tx <= nx+r and ny-d <= ty and ty <= ny+u)) continue;
if (valid(tx, ty) and board[tx][ty] < board[gx][gy] and chmax(mx_nei, board[tx][ty])) mx_dir = _;
}
// debug(nx, ny, gx, gy, l, r, d, u, mx_dir, gx + dx[mx_dir], gy + dy[mx_dir]);
return mx_dir != -1 and gx + dx[mx_dir] == nx and gy + dy[mx_dir] == ny;
};
auto T = [](int l, int r, int d, int u) -> int {
return 27*l + 9*r + 3*d + 1*u;
};
vector<vector<vector<int>>> pre(81, vector<vector<int>>(H+2, vector<int>(W+2, 0)));
for (int l : {0, 1, 2}) for (int r : {0, 1, 2}) {
for (int d : {0, 1, 2}) for (int u : {0, 1, 2}) {
for (int i = 1; i <= H; ++i) for (int j = 1; j <= W; ++j) {
int deg_i = 0;
for (int _ : {0, 1, 2, 3}) deg_i += check(i, j, i+dx[_], j+dy[_], l, r, d, u);
pre[T(l, r, d, u)][i][j] = deg_i == 0;
}
}
}
for (int k = 0; k < 81; ++k) {
for (int i = 1; i <= H; ++i) {
for (int j = 1; j <= W; ++j) {
pre[k][i][j] += pre[k][i-1][j] + pre[k][i][j-1] - pre[k][i-1][j-1];
}
}
}
auto get = [&](int lay, int x1, int x2, int y1, int y2) -> int {
if (x1 > x2 or y1 > y2) return 0;
return pre[lay][x2][y2] - pre[lay][x1-1][y2] - pre[lay][x2][y1-1] + pre[lay][x1-1][y1-1];
};
int ans = 0;
for (int x1 = 1; x1 <= H; ++x1) for (int x2 = x1; x2 <= H; ++x2) {
for (int y1 = 1; y1 <= W; ++y1) for (int y2 = y1; y2 <= W; ++y2) {
// debug(x1, x2, y1, y2);
int cnt = 0;
if (x2-x1+1 <= 3 and y2-y1+1 <= 3) {
for (int x = x1; x <= x2; ++x) for (int y = y1; y <= y2; ++y) {
int deg_i = 0;
for (int _ : {0, 1, 2, 3}) deg_i += check(x, y, x+dx[_], y+dy[_], x-x1, x2-x, y-y1, y2-y);
// debug(x, y, deg_i);
cnt += deg_i == 0;
}
}
else if (x2-x1+1 == 1) {
cnt += get(T(0, 0, 0, 2), x1, x1, y1, y1) + get(T(0, 0, 1, 2), x1, x1, y1+1, y1+1);
cnt += get(T(0, 0, 2, 0), x1, x1, y2, y2) + get(T(0, 0, 2, 1), x1, x1, y2-1, y2-1);
cnt += get(T(0, 0, 2, 2), x1, x1, y1+2, y2-2);
}
else if (y2-y1+1 == 1) {
cnt += get(T(0, 2, 0, 0), x1, x1, y1, y1) + get(T(1, 2, 0, 0), x1+1, x1+1, y1, y1);
cnt += get(T(2, 0, 0, 0), x2, x2, y1, y1) + get(T(2, 1, 0, 0), x2-1, x2-1, y1, y1);
cnt += get(T(2, 2, 0, 0), x1+2, x2-2, y1, y1);
}
else if (x2-x1+1 == 2) {
cnt += get(T(0, 1, 0, 2), x1, x1, y1, y1) + get(T(0, 1, 1, 2), x1, x1, y1+1, y1+1);
cnt += get(T(0, 1, 2, 0), x1, x1, y2, y2) + get(T(0, 1, 2, 1), x1, x1, y2-1, y2-1);
cnt += get(T(0, 1, 2, 2), x1, x1, y1+2, y2-2);
cnt += get(T(1, 0, 0, 2), x2, x2, y1, y1) + get(T(1, 0, 1, 2), x2, x2, y1+1, y1+1);
cnt += get(T(1, 0, 2, 0), x2, x2, y2, y2) + get(T(1, 0, 2, 1), x2, x2, y2-1, y2-1);
cnt += get(T(1, 0, 2, 2), x2, x2, y1+2, y2-2);
}
else if (y2-y1+1 == 2) {
cnt += get(T(0, 2, 0, 1), x1, x1, y1, y1) + get(T(1, 2, 0, 1), x1+1, x1+1, y1, y1);
cnt += get(T(2, 0, 0, 1), x2, x2, y1, y1) + get(T(2, 1, 0, 1), x2-1, x2-1, y1, y1);
cnt += get(T(2, 2, 0, 1), x1+2, x2-2, y1, y1);
cnt += get(T(0, 2, 1, 0), x1, x1, y2, y2) + get(T(1, 2, 1, 0), x1+1, x1+1, y2, y2);
cnt += get(T(2, 0, 1, 0), x2, x2, y2, y2) + get(T(2, 1, 1, 0), x2-1, x2-1, y2, y2);
cnt += get(T(2, 2, 1, 0), x1+2, x2-2, y2, y2);
}
else if (x2-x1+1 == 3) {
int x3 = x1 + 1;
cnt += get(T(0, 2, 0, 2), x1, x1, y1, y1) + get(T(0, 2, 1, 2), x1, x1, y1+1, y1+1);
cnt += get(T(0, 2, 2, 0), x1, x1, y2, y2) + get(T(0, 2, 2, 1), x1, x1, y2-1, y2-1);
cnt += get(T(0, 2, 2, 2), x1, x1, y1+2, y2-2);
cnt += get(T(2, 0, 0, 2), x2, x2, y1, y1) + get(T(2, 0, 1, 2), x2, x2, y1+1, y1+1);
cnt += get(T(2, 0, 2, 0), x2, x2, y2, y2) + get(T(2, 0, 2, 1), x2, x2, y2-1, y2-1);
cnt += get(T(2, 0, 2, 2), x2, x2, y1+2, y2-2);
cnt += get(T(1, 1, 0, 2), x3, x3, y1, y1) + get(T(1, 1, 1, 2), x3, x3, y1+1, y1+1);
cnt += get(T(1, 1, 2, 0), x3, x3, y2, y2) + get(T(1, 1, 2, 1), x3, x3, y2-1, y2-1);
cnt += get(T(1, 1, 2, 2), x3, x3, y1+2, y2-2);
}
else if (y2-y1+1 == 3) {
int y3 = y1 + 1;
cnt += get(T(0, 2, 0, 2), x1, x1, y1, y1) + get(T(1, 2, 0, 2), x1+1, x1+1, y1, y1);
cnt += get(T(2, 0, 0, 2), x2, x2, y1, y1) + get(T(2, 1, 0, 2), x2-1, x2-1, y1, y1);
cnt += get(T(2, 2, 0, 2), x1+2, x2-2, y1, y1);
cnt += get(T(0, 2, 2, 0), x1, x1, y2, y2) + get(T(1, 2, 2, 0), x1+1, x1+1, y2, y2);
cnt += get(T(2, 0, 2, 0), x2, x2, y2, y2) + get(T(2, 1, 2, 0), x2-1, x2-1, y2, y2);
cnt += get(T(2, 2, 2, 0), x1+2, x2-2, y2, y2);
cnt += get(T(0, 2, 1, 1), x1, x1, y3, y3) + get(T(1, 2, 1, 1), x1+1, x1+1, y3, y3);
cnt += get(T(2, 0, 1, 1), x2, x2, y3, y3) + get(T(2, 1, 1, 1), x2-1, x2-1, y3, y3);
cnt += get(T(2, 2, 1, 1), x1+2, x2-2, y3, y3);
}
else {
cnt += get(T(0, 2, 0, 2), x1, x1, y1, y1) + get(T(1, 2, 1, 2), x1+1, x1+1, y1+1, y1+1);
cnt += get(T(0, 2, 2, 0), x1, x1, y2, y2) + get(T(1, 2, 2, 1), x1+1, x1+1, y2-1, y2-1);
cnt += get(T(2, 0, 0, 2), x2, x2, y1, y1) + get(T(2, 1, 1, 2), x2-1, x2-1, y1+1, y1+1);
cnt += get(T(2, 0, 2, 0), x2, x2, y2, y2) + get(T(2, 1, 2, 1), x2-1, x2-1, y2-1, y2-1);
cnt += get(T(0, 2, 1, 2), x1, x1, y1+1, y1+1) + get(T(1, 2, 0, 2), x1+1, x1+1, y1, y1);
cnt += get(T(0, 2, 2, 1), x1, x1, y2-1, y2-1) + get(T(1, 2, 2, 0), x1+1, x1+1, y2, y2);
cnt += get(T(2, 0, 1, 2), x2, x2, y1+1, y1+1) + get(T(2, 1, 0, 2), x2-1, x2-1, y1, y1);
cnt += get(T(2, 0, 2, 1), x2, x2, y2-1, y2-1) + get(T(2, 1, 2, 0), x2-1, x2-1, y2, y2);
cnt += get(T(0, 2, 2, 2), x1, x1, y1+2, y2-2) + get(T(1, 2, 2, 2), x1+1, x1+1, y1+2, y2-2);
cnt += get(T(2, 0, 2, 2), x2, x2, y1+2, y2-2) + get(T(2, 1, 2, 2), x2-1, x2-1, y1+2, y2-2);
cnt += get(T(2, 2, 0, 2), x1+2, x2-2, y1, y1) + get(T(2, 2, 1, 2), x1+2, x2-2, y1+1, y1+1);
cnt += get(T(2, 2, 2, 0), x1+2, x2-2, y2, y2) + get(T(2, 2, 2, 1), x1+2, x2-2, y2-1, y2-1);
cnt += get(T(2, 2, 2, 2), x1+2, x2-2, y1+2, y2-2);
}
if (cnt == 1) ++ans;
}
}
cout << ans << "\n";
}
int32_t main() {
fastIO();
int t = 1; // cin >> t;
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:60:28: error: return-statement with a value, in function returning 'void' [-fpermissive]
60 | return cout << ans << "\n";
| ~~~~~~~~~~~~^~~~~~~
