Submission #527918

#	Time	Username	Problem	Language	Result	Execution time	Memory
527918		SorahISA	Sandcastle 2 (JOI22_ho_t5)	C++17	80 / 100	5085 ms	227648 KiB

Main

#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;
    
    if (H == 1) {
        vector<int> board(W);
        for (int &x : board) cin >> x;
        
        int ans = W;
        for (int i = 1, flag = 0, len = 0; i < W; ++i) {
                 if (flag == 0 and board[i] > board[i-1]) flag = 1, len = 0;
            else if (flag == 1 and board[i] < board[i-1]) flag = 0, len = 0;
            ans += ++len;
        }
        return cout << ans << "\n", void();
    }
    
    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: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 56 / 56
• Subtask 5: 0 / 20