oj.uz

Submission #831478

# Submission time Handle Problem Language Result Execution time Memory
831478 2023-08-20T09:37:01 Z green_gold_dog Sandcastle 2 (JOI22_ho_t5) C++17
80 / 100
 735 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<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;
                                                        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 1 ms 340 KB Output is correct
2 Correct 434 ms 386228 KB Output is correct
3 Correct 413 ms 379376 KB Output is correct
4 Correct 422 ms 386184 KB Output is correct
5 Correct 410 ms 386148 KB Output is correct
6 Correct 417 ms 386184 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 2 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 1096 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 2 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 1096 KB Output is correct
7 Correct 13 ms 11860 KB Output is correct
8 Correct 13 ms 11860 KB Output is correct
9 Correct 37 ms 28312 KB Output is correct
10 Correct 33 ms 25908 KB Output is correct
11 Correct 12 ms 10828 KB Output is correct
12 Correct 12 ms 10836 KB Output is correct
13 Correct 39 ms 29492 KB Output is correct
14 Correct 23 ms 18584 KB Output is correct
15 Correct 32 ms 25888 KB Output is correct
16 Correct 31 ms 25836 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 2 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 1096 KB Output is correct
7 Correct 13 ms 11860 KB Output is correct
8 Correct 13 ms 11860 KB Output is correct
9 Correct 37 ms 28312 KB Output is correct
10 Correct 33 ms 25908 KB Output is correct
11 Correct 12 ms 10828 KB Output is correct
12 Correct 12 ms 10836 KB Output is correct
13 Correct 39 ms 29492 KB Output is correct
14 Correct 23 ms 18584 KB Output is correct
15 Correct 32 ms 25888 KB Output is correct
16 Correct 31 ms 25836 KB Output is correct
17 Correct 60 ms 54340 KB Output is correct
18 Correct 218 ms 177564 KB Output is correct
19 Correct 91 ms 70600 KB Output is correct
20 Correct 367 ms 254016 KB Output is correct
21 Correct 380 ms 262536 KB Output is correct
22 Correct 373 ms 262548 KB Output is correct
23 Correct 360 ms 253536 KB Output is correct
24 Correct 281 ms 187844 KB Output is correct
25 Correct 353 ms 235740 KB Output is correct
26 Correct 397 ms 247276 KB Output is correct
27 Correct 366 ms 235736 KB Output is correct
28 Correct 361 ms 247272 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 2 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 1096 KB Output is correct
7 Correct 13 ms 11860 KB Output is correct
8 Correct 13 ms 11860 KB Output is correct
9 Correct 37 ms 28312 KB Output is correct
10 Correct 33 ms 25908 KB Output is correct
11 Correct 12 ms 10828 KB Output is correct
12 Correct 12 ms 10836 KB Output is correct
13 Correct 39 ms 29492 KB Output is correct
14 Correct 23 ms 18584 KB Output is correct
15 Correct 32 ms 25888 KB Output is correct
16 Correct 31 ms 25836 KB Output is correct
17 Correct 60 ms 54340 KB Output is correct
18 Correct 218 ms 177564 KB Output is correct
19 Correct 91 ms 70600 KB Output is correct
20 Correct 367 ms 254016 KB Output is correct
21 Correct 380 ms 262536 KB Output is correct
22 Correct 373 ms 262548 KB Output is correct
23 Correct 360 ms 253536 KB Output is correct
24 Correct 281 ms 187844 KB Output is correct
25 Correct 353 ms 235740 KB Output is correct
26 Correct 397 ms 247276 KB Output is correct
27 Correct 366 ms 235736 KB Output is correct
28 Correct 361 ms 247272 KB Output is correct
29 Correct 439 ms 386040 KB Output is correct
30 Runtime error 735 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -