//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;
constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;
random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());
template<typename T>
bool assign_max(T& a, T b) {
if (b > a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_min(T& a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
T square(T a) {
return a * a;
}
template<>
struct std::hash<pair<ll, ll>> {
ll operator() (pair<ll, ll> p) const {
return ((__int128)p.first * MOD + p.second) % INF64;
}
};
ll get(vector<vector<vector<vector<vector<vector<ll>>>>>>& dp2, vector<vector<vector<vector<vector<vector<ll>>>>>>& pref, ll x1, ll y1, ll x2, ll y2, ll xg) {
ll bu = min(2, xg - x1), bd = min(2, x2 - xg);
if (y2 - y1 > 4) {
return pref[xg][y2 - 2][bu][2][bd][2] - pref[xg][y1 + 2][bu][2][bd][2] + dp2[xg][y1][bu][0][bd][2] + dp2[xg][y1 + 1][bu][1][bd][2] + dp2[xg][y2 - 1][bu][2][bd][0] + dp2[xg][y2 - 2][bu][2][bd][1];
}
if (y2 - y1 == 4) {
return dp2[xg][y1][bu][0][bd][2] + dp2[xg][y1 + 1][bu][1][bd][2] + dp2[xg][y2 - 1][bu][2][bd][0] + dp2[xg][y2 - 2][bu][2][bd][1];
}
if (y2 - y1 == 3) {
return dp2[xg][y1][bu][0][bd][2] + dp2[xg][y1 + 1][bu][1][bd][1] + dp2[xg][y2 - 1][bu][2][bd][0];
}
if (y2 - y1 == 2) {
return dp2[xg][y1][bu][0][bd][1] + dp2[xg][y2 - 1][bu][1][bd][0];
}
if (y2 - y1 == 1) {
return dp2[xg][y1][bu][0][bd][0];
}
return 0;
}
void solve() {
ll n, m;
cin >> n >> m;
bool b = false;
if (n > m) {
swap(n, m);
b = true;
}
vector<vector<ll>> arr(n, vector<ll>(m));
if (!b) {
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
} else {
for (ll i = 0; i < m; i++) {
for (ll j = 0; j < n; j++) {
cin >> arr[j][i];
}
}
}
vector<vector<vector<vector<vector<vector<ll>>>>>> dp1(n, vector(m, vector(2, vector(2, vector(2, vector<ll>(2, -1))))));
vector<vector<vector<vector<vector<vector<ll>>>>>> dp2(n, vector(m, vector(3, vector(3, vector(3, vector<ll>(3, 0))))));
vector<vector<vector<vector<vector<vector<ll>>>>>> pref(n, vector(m + 1, vector(3, vector(3, vector(3, vector<ll>(3, 0))))));
vector<vector<vector<vector<vector<ll>>>>> so(n, vector(m, vector(m, vector(3, vector<ll>(3, 0)))));
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < m; j++) {
ll mi = -1;
for (ll bu = 0; bu <= 1; bu++) {
if (bu && i == 0) {
continue;
}
ll fir = mi;
if (bu && arr[i][j] > arr[i - 1][j]) {
assign_max(mi, arr[i - 1][j]);
}
for (ll bl = 0; bl <= 1; bl++) {
if (bl && j == 0) {
continue;
}
ll fir = mi;
if (bl && arr[i][j] > arr[i][j - 1]) {
assign_max(mi, arr[i][j - 1]);
}
for (ll bd = 0; bd <= 1; bd++) {
if (bd && i == n - 1) {
continue;
}
ll fir = mi;
if (bd && arr[i][j] > arr[i + 1][j]) {
assign_max(mi, arr[i + 1][j]);
}
for (ll br = 0; br <= 1; br++) {
if (br && j == m - 1) {
continue;
}
ll fir = mi;
if (br && arr[i][j] > arr[i][j + 1]) {
assign_max(mi, arr[i][j + 1]);
}
dp1[i][j][bu][bl][bd][br] = mi;
mi = fir;
}
mi = fir;
}
mi = fir;
}
mi = fir;
}
}
}
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < m; j++) {
for (ll bu = 0; bu <= 2; bu++) {
if (i - bu < 0) {
continue;
}
for (ll bl = 0; bl <= 2; bl++) {
if (j - bl < 0) {
continue;
}
for (ll bd = 0; bd <= 2; bd++) {
if (i + bd >= n) {
continue;
}
for (ll br = 0; br <= 2; br++) {
if (j + br >= m) {
continue;
}
if (bu) {
dp2[i][j][bu][bl][bd][br] += arr[i][j] == dp1[i - 1][j][bu - 1][min(bl, 1)][1][min(br, 1)];
}
if (bd) {
dp2[i][j][bu][bl][bd][br] += arr[i][j] == dp1[i + 1][j][1][min(bl, 1)][bd - 1][min(br, 1)];
}
if (bl) {
dp2[i][j][bu][bl][bd][br] += arr[i][j] == dp1[i][j - 1][min(bu, 1)][bl - 1][min(bd, 1)][1];
}
if (br) {
dp2[i][j][bu][bl][bd][br] += arr[i][j] == dp1[i][j + 1][min(bu, 1)][1][min(bd, 1)][br - 1];
}
dp2[i][j][bu][bl][bd][br] ^= 1;
pref[i][j + 1][bu][bl][bd][br] = pref[i][j][bu][bl][bd][br] + dp2[i][j][bu][bl][bd][br];
}
}
}
}
}
}
ll ans = 0;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < m; j++) {
for (ll k = j + 1; k <= m; k++) {
ll na = 0;
for (ll aj = 0; aj + i < n; aj++) {
ll ns = 0, sna = na;
if (aj >= 3) {
na += ns += get(dp2, pref, i, j, i + aj, k, i + aj - 3);
if (na > 1) {
break;
}
}
for (ll naj = max(0, aj - 2); naj <= aj; naj++) {
ns += get(dp2, pref, i, j, i + aj, k, i + naj);
if (sna + ns > 1) {
break;
}
}
if (ns + sna == 1) {
ans++;
}
}
}
}
}
cout << ans << '\n';
}
int main() {
if (IS_FILE) {
freopen("", "r", stdin);
freopen("", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll t = 1;
if (IS_TEST_CASES) {
cin >> t;
}
for (ll i = 0; i < t; i++) {
solve();
}
}
Compilation message
Main.cpp:12:22: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '9000000000000000000' to '-494665728' [-Woverflow]
12 | constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007;
| ^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:211:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
211 | freopen("", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:212:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
212 | freopen("", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
977 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
941 ms |
888088 KB |
Output is correct |
| 8 |
Correct |
933 ms |
888080 KB |
Output is correct |
| 9 |
Correct |
24 ms |
19416 KB |
Output is correct |
| 10 |
Correct |
66 ms |
22344 KB |
Output is correct |
| 11 |
Correct |
349 ms |
337520 KB |
Output is correct |
| 12 |
Correct |
316 ms |
337508 KB |
Output is correct |
| 13 |
Correct |
22 ms |
17876 KB |
Output is correct |
| 14 |
Correct |
15 ms |
11616 KB |
Output is correct |
| 15 |
Correct |
27 ms |
22348 KB |
Output is correct |
| 16 |
Correct |
27 ms |
22284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
941 ms |
888088 KB |
Output is correct |
| 8 |
Correct |
933 ms |
888080 KB |
Output is correct |
| 9 |
Correct |
24 ms |
19416 KB |
Output is correct |
| 10 |
Correct |
66 ms |
22344 KB |
Output is correct |
| 11 |
Correct |
349 ms |
337520 KB |
Output is correct |
| 12 |
Correct |
316 ms |
337508 KB |
Output is correct |
| 13 |
Correct |
22 ms |
17876 KB |
Output is correct |
| 14 |
Correct |
15 ms |
11616 KB |
Output is correct |
| 15 |
Correct |
27 ms |
22348 KB |
Output is correct |
| 16 |
Correct |
27 ms |
22284 KB |
Output is correct |
| 17 |
Runtime error |
724 ms |
1048576 KB |
Execution killed with signal 9 |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
980 KB |
Output is correct |
| 4 |
Correct |
1 ms |
980 KB |
Output is correct |
| 5 |
Correct |
1 ms |
980 KB |
Output is correct |
| 6 |
Correct |
1 ms |
980 KB |
Output is correct |
| 7 |
Correct |
941 ms |
888088 KB |
Output is correct |
| 8 |
Correct |
933 ms |
888080 KB |
Output is correct |
| 9 |
Correct |
24 ms |
19416 KB |
Output is correct |
| 10 |
Correct |
66 ms |
22344 KB |
Output is correct |
| 11 |
Correct |
349 ms |
337520 KB |
Output is correct |
| 12 |
Correct |
316 ms |
337508 KB |
Output is correct |
| 13 |
Correct |
22 ms |
17876 KB |
Output is correct |
| 14 |
Correct |
15 ms |
11616 KB |
Output is correct |
| 15 |
Correct |
27 ms |
22348 KB |
Output is correct |
| 16 |
Correct |
27 ms |
22284 KB |
Output is correct |
| 17 |
Runtime error |
724 ms |
1048576 KB |
Execution killed with signal 9 |
| 18 |
Halted |
0 ms |
0 KB |
- |
