Submission #941459

#	Time	Username	Problem	Language	Result	Execution time	Memory
941459		peterandvoi	Sandcastle 2 (JOI22_ho_t5)	C++17	100 / 100	373 ms	17588 KiB

Main

// Radewoosh approach, but i found out a solution to solve the problem in O(n * m * min(n, m))

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a;
    if (n < m) {
        a.resize(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                cin >> a[i][j];
            }
        }
    } else {
        a.resize(m + 1, vector<int>(n + 1));
        for (int i = n; i >= 1; --i) {
            for (int j = 1; j <= m; ++j) {
                cin >> a[j][i];
            }
        }
        swap(n, m);
    }
    vector<int> value;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            value.emplace_back(a[i][j]);
        }
    }
    sort(value.begin(), value.end());
    value.erase(unique(value.begin(), value.end()), value.end());
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            a[i][j] = lower_bound(value.begin(), value.end(), a[i][j]) - value.begin() + 1;
        }
    }
    vector<vector<vector<long long>>> diff(16, vector<vector<long long>>(n + 1, vector<long long>(m + 1)));
    auto inside = [&](int i, int j) {
        return 1 <= i && i <= n && 1 <= j && j <= m;
    };
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int mask = 0; mask < 16; ++mask) {
                int mx = 0, mn = n * m + 1;
                for (int dr = 0; dr < 4; ++dr) {
                    if (mask >> dr & 1) {
                        int x = i + dx[dr];
                        int y = j + dy[dr];
                        if (inside(x, y)) {
                            if (a[x][y] < a[i][j]) {
                                mx = max(mx, a[x][y]);
                            } else {
                                mn = min(mn, a[x][y]);
                            }
                        }
                    }
                }
                diff[mask][i][j] = a[i][j] - mx + (mn == n * m + 1) * (mn - a[i][j]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int mask = 0; mask < 16; ++mask) {
                diff[mask][i][j] += diff[mask][i - 1][j];
                diff[mask][i][j] += diff[mask][i][j - 1];
                diff[mask][i][j] -= diff[mask][i - 1][j - 1];
            }
        }
    }
    auto get_rect = [&](int mask, int i, int j, int x, int y) -> long long {
        if (i > x || j > y) {
            return 0;
        }
        return diff[mask][x][y] - diff[mask][i - 1][y] - diff[mask][x][j - 1] + diff[mask][i - 1][j - 1];
    };
    vector<long long> L(m + 1), mid(m + 1), R(m + 1);
    auto get = [&](const vector<long long> &v, int l, int r) -> long long {
        return l <= r ? v[r] - v[l - 1] : 0;
    };
    auto count_matches = [&](const vector<pair<long long, int>> &a, const vector<pair<long long, int>> &b) {
        int res = 0;
        int n = (int) a.size(), m = (int) b.size();
        int L = n - 1, R = n - 1;
        for (int i = m - 1; i >= 0; --i) {
            while (R >= 0 && a[R].first > b[i].first) {
                R--;
                L = R;
            }
            while (a[L].first == b[i].first && L - 1 >= 0 && a[L - 1] > b[i]) {
                L--;
            }
            if (L >= 0 && L <= R && a[L].first == a[R].first && a[L].first == b[i].first && a[L].second > b[i].second) {
                res += R - L + 1;
            }
        }
        return res;
    };
    auto solve = [&](int r1, int r2) {
        int res = 0;
        vector<pair<long long, int>> needs, candidates;
        for (int c = 1; c <= m; ++c) {
            { // only column c
                if (r1 == r2) {
                    res++;
                } else {
                    long long sum_dif = 0;
                    sum_dif += get_rect(4, r1, c, r1, c);
                    sum_dif += get_rect(1, r2, c, r2, c);
                    sum_dif += get_rect(5, r1 + 1, c, r2 - 1, c);
                    res += sum_dif == n * m + 1;
                }
            }
            { // mid
                if (r1 != r2) {
                    mid[c] = mid[c - 1];
                    mid[c] += get_rect(14, r1, c, r1, c);
                    mid[c] += get_rect(15, r1 + 1, c, r2 - 1, c);
                    mid[c] += get_rect(11, r2, c, r2, c);
                } else {
                    mid[c] = mid[c - 1] + get_rect(10, r1, c, r1, c);
                }
            }
            { // left
                if (r1 != r2) {
                    L[c] = L[c - 1];
                    L[c] += get_rect(6, r1, c, r1, c);
                    L[c] += get_rect(7, r1 + 1, c, r2 - 1, c);
                    L[c] += get_rect(3, r2, c, r2, c);
                } else {
                    L[c] = L[c - 1] + get_rect(2, r1, c, r1, c);
                }
            }
            { // right
                if (r1 != r2) {
                    R[c] = R[c - 1];
                    R[c] += get_rect(12, r1, c, r1, c);
                    R[c] += get_rect(13, r1 + 1, c, r2 - 1, c);
                    R[c] += get_rect(9, r2, c, r2, c);
                } else {
                    R[c] = R[c - 1] + get_rect(8, r1, c, r1, c);
                }
            }
            if (c > 1) {
                needs.emplace_back(get(R, c, c) + get(mid, 1, c - 1), c);
            }
            if (c < m) {
                candidates.emplace_back(n * m + 1 - get(L, c, c) + get(mid, 1, c), c);
            }
        }
        sort(needs.begin(), needs.end());
        sort(candidates.begin(), candidates.end());
        res += count_matches(needs, candidates);
        return res;
    };
    long long res = 0;
    for (int r1 = 1; r1 <= n; ++r1) {
        for (int r2 = r1; r2 <= n; ++r2) {
            res += solve(r1, r2);
        }
    }
    cout << res;
}

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