//#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, NR = 5;
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 + 1, vector(3, vector<ll>(3, 0)))));
vector<vector<vector<vector<vector<ll>>>>> sop(n, vector(m, vector(m + 1, vector(3, vector<ll>(3, 0)))));
vector<vector<vector<ll>>> psop1(n + 1, vector(m, vector(m + 1, 0)));
vector<vector<vector<ll>>> psop0(n + 1, vector(m, vector(m + 1, 0)));
vector<vector<vector<ll>>> b1(n + 1, vector(m, vector(m + 1, n - 1)));
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];
}
}
}
}
}
}
for (ll i = n - 1; i >= 0; i--) {
for (ll j = 0; j < m; j++) {
for (ll k = j + 1; k <= m; k++) {
for (ll bu = 0; bu <= 2; bu++) {
if (i - bu < 0) {
continue;
}
for (ll bd = 0; bd <= 2; bd++) {
if (i + bd >= n) {
continue;
}
so[i][j][k][bu][bd] = get(dp2, pref, i - bu, j, i + bd, k, i);
if (bu == 2 && bd == 2) {
if (so[i][j][k][2][2] >= 1) {
b1[i][j][k] = i;
} else {
b1[i][j][k] = b1[i + 1][j][k];
}
}
}
}
}
}
}
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < m; j++) {
for (ll k = j + 1; k <= m; k++) {
for (ll bu = 0; bu <= 2; bu++) {
if (i - bu < 0) {
continue;
}
for (ll bd = 0; bd <= 2; bd++) {
if (i + bd >= n) {
continue;
}
sop[i][j][k][bu][bd] = so[i][j][k][bu][bd] + (bd > 0 ? so[i + 1][j][k][min(2, bu + 1)][bd - 1] : 0);
if (bu == 2 && bd == 1) {
psop1[i + 1][j][k] = psop1[i][j][k] + (sop[i][j][k][bu][bd] == 1);
psop0[i + 1][j][k] = psop0[i][j][k] + (sop[i][j][k][bu][bd] == 0);
}
}
}
}
}
}
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;
ll aj = 0;
for (;aj + i < n && aj < NR; aj++) {
ll naj = max(0, aj - 1);
if (na + sop[i + naj][j][k][min(2, naj)][aj - naj] == 1) {
ans++;
}
if (aj >= 1) {
na += so[i + aj - 1][j][k][min(2, aj - 1)][2];
if (na > 1) {
break;
}
}
}
if (i + aj == n) {
continue;
}
ll npos = i + aj - 1;
while (na <= 1 && npos < n) {
ll no = b1[npos][j][k];
if (na) {
ans += psop0[no + 1][j][k] - psop0[npos][j][k];
} else {
ans += psop1[no + 1][j][k] - psop1[npos][j][k];
}
na += so[no][j][k][2][2];
npos = no + 1;
}
}
}
}
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, NR = 5;
| ^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:269:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
269 | freopen("", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:270:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
270 | freopen("", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
430 ms |
386104 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
