oj.uz

Submission #831470

# Submission time Handle Problem Language Result Execution time Memory
831470 2023-08-20T09:30:52 Z green_gold_dog Sandcastle 2 (JOI22_ho_t5) C++17
80 / 100
 839 ms 1048576 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, NR = 3;
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);
                                                }
                                        }
                                }
                                psop1[n][j][k] = psop1[n - 1][j][k];
                                psop0[n][j][k] = psop0[n - 1][j][k];
                        }
                }
        }
        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 = 3;
      |                      ^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:271:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  271 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:272:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  272 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 415 ms 385960 KB Output is correct
3 Correct 415 ms 379520 KB Output is correct
4 Correct 408 ms 386096 KB Output is correct
5 Correct 411 ms 386228 KB Output is correct
6 Correct 414 ms 386232 KB Output is correct

Subtask #2
10.0 / 10.0

# 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 Correct 1 ms 1236 KB Output is correct
4 Correct 2 ms 1276 KB Output is correct
5 Correct 1 ms 1236 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 1 ms 980 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 2 ms 1276 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 13 ms 11860 KB Output is correct
8 Correct 12 ms 11912 KB Output is correct
9 Correct 34 ms 28660 KB Output is correct
10 Correct 37 ms 26160 KB Output is correct
11 Correct 12 ms 10836 KB Output is correct
12 Correct 12 ms 10836 KB Output is correct
13 Correct 43 ms 29828 KB Output is correct
14 Correct 22 ms 18720 KB Output is correct
15 Correct 40 ms 26240 KB Output is correct
16 Correct 39 ms 26196 KB Output is correct

Subtask #4
56.0 / 56.0

# 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 Correct 1 ms 1236 KB Output is correct
4 Correct 2 ms 1276 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 13 ms 11860 KB Output is correct
8 Correct 12 ms 11912 KB Output is correct
9 Correct 34 ms 28660 KB Output is correct
10 Correct 37 ms 26160 KB Output is correct
11 Correct 12 ms 10836 KB Output is correct
12 Correct 12 ms 10836 KB Output is correct
13 Correct 43 ms 29828 KB Output is correct
14 Correct 22 ms 18720 KB Output is correct
15 Correct 40 ms 26240 KB Output is correct
16 Correct 39 ms 26196 KB Output is correct
17 Correct 61 ms 54296 KB Output is correct
18 Correct 267 ms 179924 KB Output is correct
19 Correct 90 ms 70852 KB Output is correct
20 Correct 366 ms 257452 KB Output is correct
21 Correct 370 ms 266236 KB Output is correct
22 Correct 375 ms 266232 KB Output is correct
23 Correct 375 ms 257040 KB Output is correct
24 Correct 292 ms 190236 KB Output is correct
25 Correct 347 ms 238652 KB Output is correct
26 Correct 362 ms 250256 KB Output is correct
27 Correct 352 ms 238640 KB Output is correct
28 Correct 364 ms 250224 KB Output is correct

Subtask #5
0 / 20.0

# 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 Correct 1 ms 1236 KB Output is correct
4 Correct 2 ms 1276 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 13 ms 11860 KB Output is correct
8 Correct 12 ms 11912 KB Output is correct
9 Correct 34 ms 28660 KB Output is correct
10 Correct 37 ms 26160 KB Output is correct
11 Correct 12 ms 10836 KB Output is correct
12 Correct 12 ms 10836 KB Output is correct
13 Correct 43 ms 29828 KB Output is correct
14 Correct 22 ms 18720 KB Output is correct
15 Correct 40 ms 26240 KB Output is correct
16 Correct 39 ms 26196 KB Output is correct
17 Correct 61 ms 54296 KB Output is correct
18 Correct 267 ms 179924 KB Output is correct
19 Correct 90 ms 70852 KB Output is correct
20 Correct 366 ms 257452 KB Output is correct
21 Correct 370 ms 266236 KB Output is correct
22 Correct 375 ms 266232 KB Output is correct
23 Correct 375 ms 257040 KB Output is correct
24 Correct 292 ms 190236 KB Output is correct
25 Correct 347 ms 238652 KB Output is correct
26 Correct 362 ms 250256 KB Output is correct
27 Correct 352 ms 238640 KB Output is correct
28 Correct 364 ms 250224 KB Output is correct
29 Correct 408 ms 385996 KB Output is correct
30 Runtime error 839 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -