Submission #830153

#TimeUsernameProblemLanguageResultExecution timeMemory
830153green_gold_dogSandcastle 2 (JOI22_ho_t5)C++17
71 / 100
5046 ms339836 KiB
//#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...