Submission #1155642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155642		antonn	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	797 ms	227636 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    vector<vector<int>> a(h + 1, vector<int>(w + 1));
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            cin >> a[i][j];
        }
    }
    if (h < w) {
        vector<vector<int>> b(w + 1, vector<int>(h + 1));
        for (int i = 1; i <= h; ++i) {
            for (int j = 1; j <= w; ++j) {
                b[j][i] = a[i][j];
            }
        }
        swap(a, b);
        swap(h, w);
    }
    
    vector<int> vals;
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            vals.push_back(a[i][j]);
        }
    }
    sort(vals.begin(), vals.end());
    map<int, int> id;
    for (int i = 0; i < h * w; ++i) {
        id[vals[i]] = i + 1;
    }
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            a[i][j] = id[a[i][j]];
        }
    }
    
    vector<vector<vector<int>>> lower(16, vector<vector<int>>(h + 1, vector<int>(w + 1)));
    vector<vector<vector<int>>> upper(16, vector<vector<int>>(h + 1, vector<int>(w + 1)));
    vector<vector<vector<int>>> val(16, vector<vector<int>>(h + 1, vector<int>(w + 1)));
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            vector<int> neigh;
            for (int d = 0; d < 4; ++d) {
                if (i + dx[d] >= 1 && i + dx[d] <= h && j + dy[d] >= 1 && dy[d] <= w) {
                    neigh.push_back(a[i + dx[d]][j + dy[d]]);
                } else {
                    neigh.push_back(-1);
                }
            }
            for (int mask = 0; mask < (1 << 4); ++mask) {
                bool ok = 1;
                for (int b = 0; b < 4; ++b) {
                    if (mask & (1 << b)) {
                        ok &= (neigh[b] != -1);
                    }
                }
                if (ok == 0) {
                    continue;
                }
                
                lower[mask][i][j] = 0;
                upper[mask][i][j] = h * w + 1;
                for (int b = 0; b < 4; ++b) {
                    if (mask & (1 << b)) {
                        int x = neigh[b];
                        if (x < a[i][j]) lower[mask][i][j] = max(lower[mask][i][j], x);
                        if (x > a[i][j]) upper[mask][i][j] = min(upper[mask][i][j], x);
                    }
                }
                val[mask][i][j] = a[i][j] - lower[mask][i][j] + (upper[mask][i][j] == h * w + 1) * (h * w + 1 - a[i][j]);
            }
        }
    }
    
    vector<vector<vector<ll>>> sum(16, vector<vector<ll>>(h + 1, vector<ll>(w + 1)));
    for (int mask = 0; mask < (1 << 4); ++mask) {
        for (int i = 1; i <= h; ++i) {
            for (int j = 1; j <= w; ++j) {
                sum[mask][i][j] = sum[mask][i - 1][j] + sum[mask][i][j - 1] - sum[mask][i - 1][j - 1] + val[mask][i][j];
            }
        }
    }

    ll ans = 0;
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            if (val[0][i][j] == h * w + 1) {
                ++ans;
            }
        }
    }
    for (int i = 1; i <= h; ++i) {
        map<int, int> cnt;
        ll sum = 0;
        for (int j = 1; j <= w; ++j) {
            ans += cnt[val[1][i][j] + sum - (h * w + 1)];
            sum += val[3][i][j];
            ++cnt[sum - val[2][i][j]];
        }
    }
    for (int j = 1; j <= w; ++j) {
        map<int, int> cnt;
        ll sum = 0;
        for (int i = 1; i <= h; ++i) {
            ans += cnt[val[4][i][j] + sum - (h * w + 1)];
            sum += val[12][i][j];
            ++cnt[sum - val[8][i][j]];
        }
    }
    
    vector<vector<vector<ll>>> pref(16, vector<vector<ll>>(h + 1, vector<ll>(w + 1)));
    for (int i = 1; i <= h; ++i) {
        for (int j = 1; j <= w; ++j) {
            pref[7][i][j] = pref[7][i][j - 1] + val[7][i][j];
            pref[11][i][j] = pref[11][i][j - 1] + val[11][i][j];
            
            pref[13][i][j] = pref[13][i - 1][j] + val[13][i][j];
            pref[14][i][j] = pref[14][i - 1][j] + val[14][i][j];
        }
    }
    for (int j = 1; j <= w; ++j) {
        for (int y = 1; y <= j - 1; ++y) {
            map<int, int> cnt;
            for (int i = 1; i <= h; ++i) {
                ans += cnt[val[5][i][j] + val[6][i][y] + (sum[15][i - 1][j - 1] - sum[15][i - 1][y]) + (pref[7][i][j - 1] - pref[7][i][y]) + pref[14][i - 1][y] + pref[13][i - 1][j] - (h * w + 1)];
                ++cnt[pref[14][i][y] + pref[13][i][j] + sum[15][i][j - 1] - sum[15][i][y] - (pref[11][i][j - 1] - pref[11][i][y]) - val[10][i][y] - val[9][i][j]];
            }
        }
    }
    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