oj.uz

Submission #831483

# Submission time Handle Problem Language Result Execution time Memory
831483 2023-08-20T09:41:34 Z green_gold_dog Sandcastle 2 (JOI22_ho_t5) C++17
80 / 100
 709 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 (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: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 1 ms 340 KB Output is correct
2 Correct 412 ms 386204 KB Output is correct
3 Correct 408 ms 379372 KB Output is correct
4 Correct 414 ms 386036 KB Output is correct
5 Correct 418 ms 386232 KB Output is correct
6 Correct 413 ms 386168 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 968 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 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 968 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 1 ms 1096 KB Output is correct
7 Correct 13 ms 11852 KB Output is correct
8 Correct 13 ms 11912 KB Output is correct
9 Correct 35 ms 28296 KB Output is correct
10 Correct 33 ms 25944 KB Output is correct
11 Correct 11 ms 10836 KB Output is correct
12 Correct 12 ms 10836 KB Output is correct
13 Correct 37 ms 29484 KB Output is correct
14 Correct 23 ms 18592 KB Output is correct
15 Correct 33 ms 25908 KB Output is correct
16 Correct 33 ms 25940 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 968 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 1 ms 1096 KB Output is correct
7 Correct 13 ms 11852 KB Output is correct
8 Correct 13 ms 11912 KB Output is correct
9 Correct 35 ms 28296 KB Output is correct
10 Correct 33 ms 25944 KB Output is correct
11 Correct 11 ms 10836 KB Output is correct
12 Correct 12 ms 10836 KB Output is correct
13 Correct 37 ms 29484 KB Output is correct
14 Correct 23 ms 18592 KB Output is correct
15 Correct 33 ms 25908 KB Output is correct
16 Correct 33 ms 25940 KB Output is correct
17 Correct 59 ms 54448 KB Output is correct
18 Correct 213 ms 177560 KB Output is correct
19 Correct 107 ms 70504 KB Output is correct
20 Correct 374 ms 254084 KB Output is correct
21 Correct 383 ms 262604 KB Output is correct
22 Correct 390 ms 262580 KB Output is correct
23 Correct 379 ms 253520 KB Output is correct
24 Correct 279 ms 187816 KB Output is correct
25 Correct 360 ms 235740 KB Output is correct
26 Correct 370 ms 247216 KB Output is correct
27 Correct 375 ms 235696 KB Output is correct
28 Correct 378 ms 247228 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 968 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1228 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 1 ms 1096 KB Output is correct
7 Correct 13 ms 11852 KB Output is correct
8 Correct 13 ms 11912 KB Output is correct
9 Correct 35 ms 28296 KB Output is correct
10 Correct 33 ms 25944 KB Output is correct
11 Correct 11 ms 10836 KB Output is correct
12 Correct 12 ms 10836 KB Output is correct
13 Correct 37 ms 29484 KB Output is correct
14 Correct 23 ms 18592 KB Output is correct
15 Correct 33 ms 25908 KB Output is correct
16 Correct 33 ms 25940 KB Output is correct
17 Correct 59 ms 54448 KB Output is correct
18 Correct 213 ms 177560 KB Output is correct
19 Correct 107 ms 70504 KB Output is correct
20 Correct 374 ms 254084 KB Output is correct
21 Correct 383 ms 262604 KB Output is correct
22 Correct 390 ms 262580 KB Output is correct
23 Correct 379 ms 253520 KB Output is correct
24 Correct 279 ms 187816 KB Output is correct
25 Correct 360 ms 235740 KB Output is correct
26 Correct 370 ms 247216 KB Output is correct
27 Correct 375 ms 235696 KB Output is correct
28 Correct 378 ms 247228 KB Output is correct
29 Correct 419 ms 386172 KB Output is correct
30 Runtime error 709 ms 1048576 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -