제출 #1326909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326909		defactopdiddy	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	320 ms	4932 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAX_CELLS = 50005;

uint32_t Delta_packed[MAX_CELLS][9];
int16_t C[MAX_CELLS][9];
int Pref[MAX_CELLS];
int freq[350005];

int H, W;
vector<vector<int>> A;

// Verify boundaries up to 2 cells depth
inline bool in_R(int vr, int vc, int ur, int uc, int du, int dd, int dc1, int dc2) {
    int dr = vr - ur;
    int dc = vc - uc;
    if (dr < 0 && du < 2 && dr < -du) return false;
    if (dr > 0 && dd < 2 && dr > dd) return false;
    if (dc < 0 && dc1 < 2 && dc < -dc1) return false;
    if (dc > 0 && dc2 < 2 && dc > dc2) return false;
    return true;
}

// Extract localized evaluations: 1 for valid local minima, 1 for local source mapping
int get_val(int r, int c, int du, int dd, int dc1, int dc2) {
    int minima = 1;
    int dr_n[] = {-1, 1, 0, 0};
    int dc_n[] = {0, 0, -1, 1};
    
    for (int i = 0; i < 4; ++i) {
        int nr = r + dr_n[i], nc = c + dc_n[i];
        if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
            if (A[nr][nc] < A[r][c] && in_R(nr, nc, r, c, du, dd, dc1, dc2)) {
                minima = 0; break;
            }
        }
    }
    
    int indeg0 = 1;
    for (int i = 0; i < 4; ++i) {
        int nr = r + dr_n[i], nc = c + dc_n[i];
        if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
            if (A[nr][nc] > A[r][c] && in_R(nr, nc, r, c, du, dd, dc1, dc2)) {
                bool points = true;
                for (int j = 0; j < 4; ++j) {
                    int wr = nr + dr_n[j], wc = nc + dc_n[j];
                    if (wr >= 0 && wr < H && wc >= 0 && wc < W) {
                        if (A[wr][wc] > A[r][c] && A[wr][wc] < A[nr][nc] && in_R(wr, wc, r, c, du, dd, dc1, dc2)) {
                            points = false; break;
                        }
                    }
                }
                if (points) { indeg0 = 0; break; }
            }
        }
    }
    return minima + indeg0;
}

int main() {
    // I/O Operations Speedup
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> H >> W)) return 0;

    A.assign(H, vector<int>(W));
    for (int r = 0; r < H; ++r) {
        for (int c = 0; c < W; ++c) cin >> A[r][c];
    }

    // Force constraints bound to mathematically limit execution row loops stringently 
    if (H > W) {
        vector<vector<int>> transposed(W, vector<int>(H));
        for (int r = 0; r < H; ++r) {
            for (int c = 0; c < W; ++c) transposed[c][r] = A[r][c];
        }
        swap(H, W);
        A = move(transposed);
    }

    // Offline block state evaluations mathematically mapped utilizing cache packing
    for (int r = 0; r < H; ++r) {
        for (int c = 0; c < W; ++c) {
            int id = r * W + c;
            for (int du = 0; du < 3; ++du) {
                for (int dd = 0; dd < 3; ++dd) {
                    uint32_t packed = 0;
                    for (int dc = 0; dc < 9; ++dc) {
                        int dc1 = dc / 3, dc2 = dc % 3;
                        int val = get_val(r, c, du, dd, dc1, dc2);
                        int old_val = (dd > 0) ? get_val(r, c, du, dd - 1, dc1, dc2) : 0;
                        int delta = val - old_val;
                        uint32_t bits = (delta + 2) & 7;
                        packed |= (bits << (3 * dc));
                    }
                    Delta_packed[id][du * 3 + dd] = packed;
                }
            }
        }
    }

    long long ans = 0;
    const int OFFSET = 150000;

    for (int r1 = 0; r1 < H; ++r1) {
        // Soft memory wipe optimized for localized row tracking width iteration bounds  
        for (int c = 0; c < W; ++c) {
            C[c][0] = C[c][1] = C[c][2] = C[c][3] = C[c][4] = 
            C[c][5] = C[c][6] = C[c][7] = C[c][8] = 0;
        }
        
        for (int r2 = r1; r2 < H; ++r2) {
            for (int step = 0; step <= 2; ++step) {
                int r = r2 - step;
                if (r < r1) break;
                int state = min(2, r - r1) * 3 + step;
                int base_id = r * W;
                
                // Bitwise unpack transitions dynamically avoiding massive if-conditions
                for (int c = 0; c < W; ++c) {
                    uint32_t packed = Delta_packed[base_id + c][state];
                    C[c][0] += (packed & 7) - 2;
                    C[c][1] += ((packed >> 3) & 7) - 2;
                    C[c][2] += ((packed >> 6) & 7) - 2;
                    C[c][3] += ((packed >> 9) & 7) - 2;
                    C[c][4] += ((packed >> 12) & 7) - 2;
                    C[c][5] += ((packed >> 15) & 7) - 2;
                    C[c][6] += ((packed >> 18) & 7) - 2;
                    C[c][7] += ((packed >> 21) & 7) - 2;
                    C[c][8] += ((packed >> 24) & 7) - 2;
                }
            }
            
            for (int c = 0; c < W; ++c) if (C[c][0] == 2) ans++;
            for (int c = 0; c < W - 1; ++c) if (C[c][1] + C[c+1][3] == 2) ans++;
            for (int c = 0; c < W - 2; ++c) if (C[c][2] + C[c+1][4] + C[c+2][6] == 2) ans++;
            
            if (W >= 4) {
                Pref[0] = C[0][8];
                for (int c = 1; c < W; ++c) Pref[c] = Pref[c-1] + C[c][8];
                
                for (int c2 = 3; c2 < W; ++c2) {
                    int c1 = c2 - 3;
                    int Y = C[c1][2] + C[c1+1][5] - Pref[c1+1];
                    freq[(2 - Y) + OFFSET]++;
                    
                    int X = C[c2-1][7] + C[c2][6] + Pref[c2-2];
                    ans += freq[X + OFFSET];
                }
                
                for (int c2 = 3; c2 < W; ++c2) {
                    int c1 = c2 - 3;
                    int Y = C[c1][2] + C[c1+1][5] - Pref[c1+1];
                    freq[(2 - Y) + OFFSET]--;
                }
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 56 / 56
• Subtask 5: 20 / 20