oj.uz

Submission #831436

# Submission time Handle Problem Language Result Execution time Memory
831436 2023-08-20T08:58:06 Z green_gold_dog Sandcastle 2 (JOI22_ho_t5) C++17
71 / 100
 5000 ms 386304 KB 
//#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] = 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;
                                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();
        }
}

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:254:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  254 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:255:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  255 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 5079 ms 385816 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 20 ms 11860 KB Output is correct
8 Correct 13 ms 11864 KB Output is correct
9 Correct 35 ms 28628 KB Output is correct
10 Correct 41 ms 26060 KB Output is correct
11 Correct 19 ms 10860 KB Output is correct
12 Correct 24 ms 10820 KB Output is correct
13 Correct 50 ms 29784 KB Output is correct
14 Correct 24 ms 18768 KB Output is correct
15 Correct 33 ms 26132 KB Output is correct
16 Correct 33 ms 26096 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 20 ms 11860 KB Output is correct
8 Correct 13 ms 11864 KB Output is correct
9 Correct 35 ms 28628 KB Output is correct
10 Correct 41 ms 26060 KB Output is correct
11 Correct 19 ms 10860 KB Output is correct
12 Correct 24 ms 10820 KB Output is correct
13 Correct 50 ms 29784 KB Output is correct
14 Correct 24 ms 18768 KB Output is correct
15 Correct 33 ms 26132 KB Output is correct
16 Correct 33 ms 26096 KB Output is correct
17 Correct 249 ms 54420 KB Output is correct
18 Correct 269 ms 179920 KB Output is correct
19 Correct 91 ms 70812 KB Output is correct
20 Correct 1304 ms 257452 KB Output is correct
21 Correct 385 ms 266296 KB Output is correct
22 Correct 439 ms 266128 KB Output is correct
23 Correct 394 ms 256732 KB Output is correct
24 Correct 310 ms 190240 KB Output is correct
25 Correct 348 ms 238812 KB Output is correct
26 Correct 361 ms 250280 KB Output is correct
27 Correct 389 ms 238736 KB Output is correct
28 Correct 372 ms 250276 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 20 ms 11860 KB Output is correct
8 Correct 13 ms 11864 KB Output is correct
9 Correct 35 ms 28628 KB Output is correct
10 Correct 41 ms 26060 KB Output is correct
11 Correct 19 ms 10860 KB Output is correct
12 Correct 24 ms 10820 KB Output is correct
13 Correct 50 ms 29784 KB Output is correct
14 Correct 24 ms 18768 KB Output is correct
15 Correct 33 ms 26132 KB Output is correct
16 Correct 33 ms 26096 KB Output is correct
17 Correct 249 ms 54420 KB Output is correct
18 Correct 269 ms 179920 KB Output is correct
19 Correct 91 ms 70812 KB Output is correct
20 Correct 1304 ms 257452 KB Output is correct
21 Correct 385 ms 266296 KB Output is correct
22 Correct 439 ms 266128 KB Output is correct
23 Correct 394 ms 256732 KB Output is correct
24 Correct 310 ms 190240 KB Output is correct
25 Correct 348 ms 238812 KB Output is correct
26 Correct 361 ms 250280 KB Output is correct
27 Correct 389 ms 238736 KB Output is correct
28 Correct 372 ms 250276 KB Output is correct
29 Execution timed out 5096 ms 386304 KB Time limit exceeded
30 Halted 0 ms 0 KB -