oj.uz

Submission #527915

# Submission time Handle Problem Language Result Execution time Memory
527915 2022-02-18T17:10:41 Z SorahISA Sandcastle 2 (JOI22_ho_t5) C++17
71 / 100
 5000 ms 227652 KB 
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int int64_t
#define double long double
using pii = pair<int, int>;
template <typename T>
using Prior = std::priority_queue<T>;
template <typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define ee emplace
#define eb emplace_back
#define ef push_front
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    cerr << "\u001b[33m" << "At func " << __FUNCTION__ << ", line " << __LINE__ << ": ",\
    cerr << "(" << #__VA_ARGS__ << ") = ",\
    _do(__VA_ARGS__),\
    cerr << "\u001b[0m"
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

const int dx[] = {1, 0,-1, 0};
const int dy[] = {0, 1, 0,-1};

void solve() {
    int H, W; cin >> H >> W;
    
    vector<vector<int>> board(H+2, vector<int>(W+2, 0));
    for (int i = 1; i <= H; ++i) for (int j = 1; j <= W; ++j) cin >> board[i][j];
    
    auto valid = [&](int x, int y) -> bool {
        return 0 <= x and x <= H+1 and 0 <= y and y <= W+1;
    };
    
    auto check = [&](int nx, int ny, int gx, int gy, int l, int r, int d, int u) -> bool {
        /// x-l, x+r, y-d, y+u ///
        if (!(nx-l <= gx and gx <= nx+r and ny-d <= gy and gy <= ny+u)) return false;
        int mx_nei = 0, mx_dir = -1;
        for (int _ : {0, 1, 2, 3}) {
            int tx = gx + dx[_], ty = gy + dy[_];
            if (!(nx-l <= tx and tx <= nx+r and ny-d <= ty and ty <= ny+u)) continue;
            if (valid(tx, ty) and board[tx][ty] < board[gx][gy] and chmax(mx_nei, board[tx][ty])) mx_dir = _;
        }
        // debug(nx, ny, gx, gy, l, r, d, u, mx_dir, gx + dx[mx_dir], gy + dy[mx_dir]);
        return mx_dir != -1 and gx + dx[mx_dir] == nx and gy + dy[mx_dir] == ny;
    };
    
    auto T = [](int l, int r, int d, int u) -> int {
        return 27*l + 9*r + 3*d + 1*u;
    };
    
    vector<vector<vector<int>>> pre(81, vector<vector<int>>(H+2, vector<int>(W+2, 0)));
    
    for (int l : {0, 1, 2}) for (int r : {0, 1, 2}) {
        for (int d : {0, 1, 2}) for (int u : {0, 1, 2}) {
            for (int i = 1; i <= H; ++i) for (int j = 1; j <= W; ++j) {
                int deg_i = 0;
                for (int _ : {0, 1, 2, 3}) deg_i += check(i, j, i+dx[_], j+dy[_], l, r, d, u);
                pre[T(l, r, d, u)][i][j] = deg_i == 0;
            }
        }
    }
    
    for (int k = 0; k < 81; ++k) {
        for (int i = 1; i <= H; ++i) {
            for (int j = 1; j <= W; ++j) {
                pre[k][i][j] += pre[k][i-1][j] + pre[k][i][j-1] - pre[k][i-1][j-1];
            }
        }
    }
    
    auto get = [&](int lay, int x1, int x2, int y1, int y2) -> int {
        if (x1 > x2 or y1 > y2) return 0;
        return pre[lay][x2][y2] - pre[lay][x1-1][y2] - pre[lay][x2][y1-1] + pre[lay][x1-1][y1-1];
    };
    
    int ans = 0;
    for (int x1 = 1; x1 <= H; ++x1) for (int x2 = x1; x2 <= H; ++x2) {
        for (int y1 = 1; y1 <= W; ++y1) for (int y2 = y1; y2 <= W; ++y2) {
            // debug(x1, x2, y1, y2);
            int cnt = 0;
            if (x2-x1+1 <= 3 and y2-y1+1 <= 3) {
                for (int x = x1; x <= x2; ++x) for (int y = y1; y <= y2; ++y) {
                    int deg_i = 0;
                    for (int _ : {0, 1, 2, 3}) deg_i += check(x, y, x+dx[_], y+dy[_], x-x1, x2-x, y-y1, y2-y);
                    // debug(x, y, deg_i);
                    cnt += deg_i == 0;
                }
            }
            else if (x2-x1+1 == 1) {
                cnt += get(T(0, 0, 0, 2), x1, x1, y1, y1) + get(T(0, 0, 1, 2), x1, x1, y1+1, y1+1);
                cnt += get(T(0, 0, 2, 0), x1, x1, y2, y2) + get(T(0, 0, 2, 1), x1, x1, y2-1, y2-1);
                cnt += get(T(0, 0, 2, 2), x1, x1, y1+2, y2-2);
            }
            else if (y2-y1+1 == 1) {
                cnt += get(T(0, 2, 0, 0), x1, x1, y1, y1) + get(T(1, 2, 0, 0), x1+1, x1+1, y1, y1);
                cnt += get(T(2, 0, 0, 0), x2, x2, y1, y1) + get(T(2, 1, 0, 0), x2-1, x2-1, y1, y1);
                cnt += get(T(2, 2, 0, 0), x1+2, x2-2, y1, y1);
            }
            else if (x2-x1+1 == 2) {
                cnt += get(T(0, 1, 0, 2), x1, x1, y1, y1) + get(T(0, 1, 1, 2), x1, x1, y1+1, y1+1);
                cnt += get(T(0, 1, 2, 0), x1, x1, y2, y2) + get(T(0, 1, 2, 1), x1, x1, y2-1, y2-1);
                cnt += get(T(0, 1, 2, 2), x1, x1, y1+2, y2-2);
                cnt += get(T(1, 0, 0, 2), x2, x2, y1, y1) + get(T(1, 0, 1, 2), x2, x2, y1+1, y1+1);
                cnt += get(T(1, 0, 2, 0), x2, x2, y2, y2) + get(T(1, 0, 2, 1), x2, x2, y2-1, y2-1);
                cnt += get(T(1, 0, 2, 2), x2, x2, y1+2, y2-2);
            }
            else if (y2-y1+1 == 2) {
                cnt += get(T(0, 2, 0, 1), x1, x1, y1, y1) + get(T(1, 2, 0, 1), x1+1, x1+1, y1, y1);
                cnt += get(T(2, 0, 0, 1), x2, x2, y1, y1) + get(T(2, 1, 0, 1), x2-1, x2-1, y1, y1);
                cnt += get(T(2, 2, 0, 1), x1+2, x2-2, y1, y1);
                cnt += get(T(0, 2, 1, 0), x1, x1, y2, y2) + get(T(1, 2, 1, 0), x1+1, x1+1, y2, y2);
                cnt += get(T(2, 0, 1, 0), x2, x2, y2, y2) + get(T(2, 1, 1, 0), x2-1, x2-1, y2, y2);
                cnt += get(T(2, 2, 1, 0), x1+2, x2-2, y2, y2);
            }
            else if (x2-x1+1 == 3) {
                int x3 = x1 + 1;
                cnt += get(T(0, 2, 0, 2), x1, x1, y1, y1) + get(T(0, 2, 1, 2), x1, x1, y1+1, y1+1);
                cnt += get(T(0, 2, 2, 0), x1, x1, y2, y2) + get(T(0, 2, 2, 1), x1, x1, y2-1, y2-1);
                cnt += get(T(0, 2, 2, 2), x1, x1, y1+2, y2-2);
                cnt += get(T(2, 0, 0, 2), x2, x2, y1, y1) + get(T(2, 0, 1, 2), x2, x2, y1+1, y1+1);
                cnt += get(T(2, 0, 2, 0), x2, x2, y2, y2) + get(T(2, 0, 2, 1), x2, x2, y2-1, y2-1);
                cnt += get(T(2, 0, 2, 2), x2, x2, y1+2, y2-2);
                cnt += get(T(1, 1, 0, 2), x3, x3, y1, y1) + get(T(1, 1, 1, 2), x3, x3, y1+1, y1+1);
                cnt += get(T(1, 1, 2, 0), x3, x3, y2, y2) + get(T(1, 1, 2, 1), x3, x3, y2-1, y2-1);
                cnt += get(T(1, 1, 2, 2), x3, x3, y1+2, y2-2);
            }
            else if (y2-y1+1 == 3) {
                int y3 = y1 + 1;
                cnt += get(T(0, 2, 0, 2), x1, x1, y1, y1) + get(T(1, 2, 0, 2), x1+1, x1+1, y1, y1);
                cnt += get(T(2, 0, 0, 2), x2, x2, y1, y1) + get(T(2, 1, 0, 2), x2-1, x2-1, y1, y1);
                cnt += get(T(2, 2, 0, 2), x1+2, x2-2, y1, y1);
                cnt += get(T(0, 2, 2, 0), x1, x1, y2, y2) + get(T(1, 2, 2, 0), x1+1, x1+1, y2, y2);
                cnt += get(T(2, 0, 2, 0), x2, x2, y2, y2) + get(T(2, 1, 2, 0), x2-1, x2-1, y2, y2);
                cnt += get(T(2, 2, 2, 0), x1+2, x2-2, y2, y2);
                cnt += get(T(0, 2, 1, 1), x1, x1, y3, y3) + get(T(1, 2, 1, 1), x1+1, x1+1, y3, y3);
                cnt += get(T(2, 0, 1, 1), x2, x2, y3, y3) + get(T(2, 1, 1, 1), x2-1, x2-1, y3, y3);
                cnt += get(T(2, 2, 1, 1), x1+2, x2-2, y3, y3);
            }
            else {
                cnt += get(T(0, 2, 0, 2), x1, x1, y1, y1) + get(T(1, 2, 1, 2), x1+1, x1+1, y1+1, y1+1);
                cnt += get(T(0, 2, 2, 0), x1, x1, y2, y2) + get(T(1, 2, 2, 1), x1+1, x1+1, y2-1, y2-1);
                cnt += get(T(2, 0, 0, 2), x2, x2, y1, y1) + get(T(2, 1, 1, 2), x2-1, x2-1, y1+1, y1+1);
                cnt += get(T(2, 0, 2, 0), x2, x2, y2, y2) + get(T(2, 1, 2, 1), x2-1, x2-1, y2-1, y2-1);
                cnt += get(T(0, 2, 1, 2), x1, x1, y1+1, y1+1) + get(T(1, 2, 0, 2), x1+1, x1+1, y1, y1);
                cnt += get(T(0, 2, 2, 1), x1, x1, y2-1, y2-1) + get(T(1, 2, 2, 0), x1+1, x1+1, y2, y2);
                cnt += get(T(2, 0, 1, 2), x2, x2, y1+1, y1+1) + get(T(2, 1, 0, 2), x2-1, x2-1, y1, y1);
                cnt += get(T(2, 0, 2, 1), x2, x2, y2-1, y2-1) + get(T(2, 1, 2, 0), x2-1, x2-1, y2, y2);
                cnt += get(T(0, 2, 2, 2), x1, x1, y1+2, y2-2) + get(T(1, 2, 2, 2), x1+1, x1+1, y1+2, y2-2);
                cnt += get(T(2, 0, 2, 2), x2, x2, y1+2, y2-2) + get(T(2, 1, 2, 2), x2-1, x2-1, y1+2, y2-2);
                cnt += get(T(2, 2, 0, 2), x1+2, x2-2, y1, y1) + get(T(2, 2, 1, 2), x1+2, x2-2, y1+1, y1+1);
                cnt += get(T(2, 2, 2, 0), x1+2, x2-2, y2, y2) + get(T(2, 2, 2, 1), x1+2, x2-2, y2-1, y2-1);
                cnt += get(T(2, 2, 2, 2), x1+2, x2-2, y1+2, y2-2);
            }
            if (cnt == 1) ++ans;
        }
    }
    cout << ans << "\n";
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Execution timed out 5070 ms 49224 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 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 33 ms 7132 KB Output is correct
8 Correct 33 ms 7116 KB Output is correct
9 Correct 42 ms 844 KB Output is correct
10 Correct 35 ms 972 KB Output is correct
11 Correct 21 ms 1312 KB Output is correct
12 Correct 25 ms 3744 KB Output is correct
13 Correct 35 ms 956 KB Output is correct
14 Correct 22 ms 716 KB Output is correct
15 Correct 39 ms 972 KB Output is correct
16 Correct 43 ms 1008 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 33 ms 7132 KB Output is correct
8 Correct 33 ms 7116 KB Output is correct
9 Correct 42 ms 844 KB Output is correct
10 Correct 35 ms 972 KB Output is correct
11 Correct 21 ms 1312 KB Output is correct
12 Correct 25 ms 3744 KB Output is correct
13 Correct 35 ms 956 KB Output is correct
14 Correct 22 ms 716 KB Output is correct
15 Correct 39 ms 972 KB Output is correct
16 Correct 43 ms 1008 KB Output is correct
17 Correct 678 ms 32412 KB Output is correct
18 Correct 757 ms 3092 KB Output is correct
19 Correct 763 ms 2996 KB Output is correct
20 Correct 693 ms 2872 KB Output is correct
21 Correct 715 ms 2896 KB Output is correct
22 Correct 667 ms 2896 KB Output is correct
23 Correct 683 ms 2856 KB Output is correct
24 Correct 534 ms 2636 KB Output is correct
25 Correct 714 ms 2940 KB Output is correct
26 Correct 755 ms 2892 KB Output is correct
27 Correct 834 ms 2928 KB Output is correct
28 Correct 692 ms 2892 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 33 ms 7132 KB Output is correct
8 Correct 33 ms 7116 KB Output is correct
9 Correct 42 ms 844 KB Output is correct
10 Correct 35 ms 972 KB Output is correct
11 Correct 21 ms 1312 KB Output is correct
12 Correct 25 ms 3744 KB Output is correct
13 Correct 35 ms 956 KB Output is correct
14 Correct 22 ms 716 KB Output is correct
15 Correct 39 ms 972 KB Output is correct
16 Correct 43 ms 1008 KB Output is correct
17 Correct 678 ms 32412 KB Output is correct
18 Correct 757 ms 3092 KB Output is correct
19 Correct 763 ms 2996 KB Output is correct
20 Correct 693 ms 2872 KB Output is correct
21 Correct 715 ms 2896 KB Output is correct
22 Correct 667 ms 2896 KB Output is correct
23 Correct 683 ms 2856 KB Output is correct
24 Correct 534 ms 2636 KB Output is correct
25 Correct 714 ms 2940 KB Output is correct
26 Correct 755 ms 2892 KB Output is correct
27 Correct 834 ms 2928 KB Output is correct
28 Correct 692 ms 2892 KB Output is correct
29 Execution timed out 5050 ms 227652 KB Time limit exceeded
30 Halted 0 ms 0 KB -