Submission #594553

#	Time	Username	Problem	Language	Result	Execution time	Memory
594553		piOOE	Sandcastle 2 (JOI22_ho_t5)	C++17	24 / 100	5042 ms	1296 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

//O((H * W)^2)
//I also came up with O((H * W)^2) solution, but didn't know how to optimize it to O(min(H, W) * H * W)
//so now this is Radewoosh's solution

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;

    bool swapped = false;
    if (n > m) {
        swapped = true;
        swap(n, m);
    }

    vector<vector<int>> a(n, vector<int>(m));
    vector<int> yy;
    for (int i = 0; i < (swapped ? m : n); ++i) {
        for (int j = 0; j < (swapped ? n : m); ++j) {
            if (!swapped) {
                cin >> a[i][j];
                yy.push_back(a[i][j]);
            } else {
                cin >> a[j][i];
                yy.push_back(a[j][i]);
            }
        }
    }

    sort(yy.begin(), yy.end());
    yy.resize(unique(yy.begin(), yy.end()) - yy.begin());

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            a[i][j] = lower_bound(yy.begin(), yy.end(), a[i][j]) - yy.begin() + 1;
        }
    }

    const int dx[4] = {-1, 0, 1, 0};
    const int dy[4] = {0, 1, 0, -1};
    //  0
    // 2 1
    //  3

    auto solveM = [&](int k) {
        ll ans = 0;
        for (int i = 0; i < m;) {
            int j = i + 1;
            while (j < m && a[k][j] < a[k][j - 1]) {
                j += 1;
            }
            int len = j - i;
            ans += len * ((ll)len - 1) / 2;
            i = j;
        }

        for (int i = m - 1; i > -1;) {
            int j = i - 1;
            while (j > -1 && a[k][j] < a[k][j + 1]) {
                j -= 1;
            }
            int len = i - j;
            ans += len * ((ll)len - 1) / 2;
            i = j;
        }

        return ans;
    };

    auto solveN = [&](int k) {
        ll ans = 0;
        for (int i = 0; i < n;) {
            int j = i + 1;
            while (j < n && a[j][k] < a[j - 1][k]) {
                j += 1;
            }
            int len = j - i;
            ans += len * ((ll)len - 1) / 2;
            i = j;
        }

        for (int i = n - 1; i > -1;) {
            int j = i - 1;
            while (j > -1 && a[j][k] < a[j + 1][k]) {
                j -= 1;
            }
            int len = i - j;
            ans += len * ((ll)len - 1) / 2;
            i = j;
        }

        return ans;
    };

    ll ans = 0;
    if (n == 1) {
        ans += solveM(0) + m;
    } else {
        int diff[16][n][m];
        memset(diff, 0, sizeof(diff));

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                for (int mask = 0; mask < 16; ++mask) {
                    int lower = 0;
                    bool big = false;
                    for (int k = 0; k < 4; ++k) {
                        if (mask >> k & 1) {
                            int nx = i + dx[k];
                            int ny = j + dy[k];
                            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                                if (a[nx][ny] < a[i][j]) {
                                    lower = max(lower, a[nx][ny]);
                                } else {
                                    big = true;
                                }
                            }
                        }
                    }
                    diff[mask][i][j] = a[i][j] - lower + (big ? 0 : n * m + 1 - a[i][j]);
                }
            }
        }

        //now handle rectangles with width or length = 1
        for (int i = 0; i < n; ++i) {
            ans += solveM(i);
        }
        for (int i = 0; i < m; ++i) {
            ans += solveN(i);
        }
        ans += n * m;

        //main part!
        for (int x1 = 0; x1 < n; ++x1) {
            for (int x2 = x1 + 1; x2 < n; ++x2) {
                for (int y1 = 0; y1 < m; ++y1) {
                    for (int y2 = y1 + 1; y2 < m; ++y2) {
                        ll sum = 0;
                        for (int i = x1; i <= x2; ++i) {
                            for (int j = y1; j <= y2; ++j) {
                                sum += diff[15 - (i == x1 ? 1 : 0) - (i == x2 ? 4 : 0) - (j == y1 ? 8 : 0) - (j == y2 ? 2 : 0)][i][j];
                            }
                        }
                        ans += (sum == (n * m + 1));
                    }
                }
                /**
                vector<ll> valMid(m), valR(m);
                for (int w1 = 0; w1 < m; ++w1) {
                    ll sum = diff[x1][w1] +
                } **/
            }
        }
    }
    cout << ans;
    return 0;
}

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