oj.uz

Submission #831489

# Submission time Handle Problem Language Result Execution time Memory
831489 2023-08-20T09:47:22 Z green_gold_dog Sandcastle 2 (JOI22_ho_t5) C++17
80 / 100
 1383 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;
        }
};
 
char get(vector<vector<vector<vector<vector<vector<char>>>>>>& 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 (char)min(2, 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 (char)min(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 == 3) {
                return (char)min(2, 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 (char)min(2, 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 (char)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<char>>>>>> dp2(n, vector(m, vector(3, vector(3, vector(3, vector<char>(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<unsigned short>>>>> so(n, vector(m, vector(m + 1, vector(3, vector<unsigned short>(3, 0)))));
        vector<vector<vector<vector<vector<unsigned short>>>>> sop(n, vector(m, vector(m + 1, vector(3, vector<unsigned short>(3, 0)))));
        vector<vector<vector<unsigned short>>> psop1(n + 1, vector(m, vector<unsigned short>(m + 1, 0)));
        vector<vector<vector<unsigned short>>> psop0(n + 1, vector(m, vector<unsigned short>(m + 1, 0)));
        vector<vector<vector<unsigned short>>> b1(n + 1, vector(m, vector<unsigned short>(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;
                                                        assign_min(dp2[i][j][bu][bl][bd][br], (char)2);
                                                        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 (get(dp2, pref, i - bu, j, i + bd, k, i) >= 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] = get(dp2, pref, i - bu, j, i + bd, k, i) + (bd > 0 ? get(dp2, pref, i - bu, j, i + bd, k, i + 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 += get(dp2, pref, i, j, aj + i + 1, k, i + aj - 1);
                                                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 += get(dp2, pref, i, j, no + 2, k, no);
                                        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:272:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  272 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:273:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |                 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 423 ms 362744 KB Output is correct
3 Correct 455 ms 356336 KB Output is correct
4 Correct 431 ms 362588 KB Output is correct
5 Correct 428 ms 362752 KB Output is correct
6 Correct 409 ms 362704 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 12 ms 11164 KB Output is correct
8 Correct 19 ms 11184 KB Output is correct
9 Correct 27 ms 17908 KB Output is correct
10 Correct 25 ms 16804 KB Output is correct
11 Correct 11 ms 9768 KB Output is correct
12 Correct 10 ms 9892 KB Output is correct
13 Correct 30 ms 18400 KB Output is correct
14 Correct 17 ms 11988 KB Output is correct
15 Correct 25 ms 16804 KB Output is correct
16 Correct 24 ms 16724 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 12 ms 11164 KB Output is correct
8 Correct 19 ms 11184 KB Output is correct
9 Correct 27 ms 17908 KB Output is correct
10 Correct 25 ms 16804 KB Output is correct
11 Correct 11 ms 9768 KB Output is correct
12 Correct 10 ms 9892 KB Output is correct
13 Correct 30 ms 18400 KB Output is correct
14 Correct 17 ms 11988 KB Output is correct
15 Correct 25 ms 16804 KB Output is correct
16 Correct 24 ms 16724 KB Output is correct
17 Correct 73 ms 51072 KB Output is correct
18 Correct 176 ms 106160 KB Output is correct
19 Correct 84 ms 52508 KB Output is correct
20 Correct 294 ms 144964 KB Output is correct
21 Correct 309 ms 148992 KB Output is correct
22 Correct 275 ms 149044 KB Output is correct
23 Correct 264 ms 144024 KB Output is correct
24 Correct 251 ms 109520 KB Output is correct
25 Correct 252 ms 135612 KB Output is correct
26 Correct 264 ms 141648 KB Output is correct
27 Correct 253 ms 135788 KB Output is correct
28 Correct 259 ms 141544 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 12 ms 11164 KB Output is correct
8 Correct 19 ms 11184 KB Output is correct
9 Correct 27 ms 17908 KB Output is correct
10 Correct 25 ms 16804 KB Output is correct
11 Correct 11 ms 9768 KB Output is correct
12 Correct 10 ms 9892 KB Output is correct
13 Correct 30 ms 18400 KB Output is correct
14 Correct 17 ms 11988 KB Output is correct
15 Correct 25 ms 16804 KB Output is correct
16 Correct 24 ms 16724 KB Output is correct
17 Correct 73 ms 51072 KB Output is correct
18 Correct 176 ms 106160 KB Output is correct
19 Correct 84 ms 52508 KB Output is correct
20 Correct 294 ms 144964 KB Output is correct
21 Correct 309 ms 148992 KB Output is correct
22 Correct 275 ms 149044 KB Output is correct
23 Correct 264 ms 144024 KB Output is correct
24 Correct 251 ms 109520 KB Output is correct
25 Correct 252 ms 135612 KB Output is correct
26 Correct 264 ms 141648 KB Output is correct
27 Correct 253 ms 135788 KB Output is correct
28 Correct 259 ms 141544 KB Output is correct
29 Correct 410 ms 362644 KB Output is correct
30 Correct 1383 ms 747852 KB Output is correct
31 Runtime error 789 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -