| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 831397 | green_gold_dog | Snowball (JOI21_ho_t2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 + 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, 0)));
vector<vector<vector<ll>>> psop0(n + 1, vector(m, vector(m, 0)));
vector<vector<vector<ll>>> b1(n + 1, vector(m, vector(m, n)));
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][bu][bd] >= 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] = psop[i][j][k] + (sop[i][j][k][bu][bd] == 1);
psop0[i + 1][j][k] = psop[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;
for (ll aj = 0; aj + i < n; aj++) {
if (aj >= 2) {
na += so[i + aj - 2][j][k][min(2, aj - 2)][2];
if (na > 1) {
break;
}
}
ll naj = max(0, aj - 1);
if (na + sop[i + naj][j][k][min(2, naj)][aj - naj] == 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();
}
}