oj.uz

Submission #594559

# Submission time Handle Problem Language Result Execution time Memory
594559 2022-07-12T16:46:31 Z piOOE Sandcastle 2 (JOI22_ho_t5) C++17
100 / 100
 2637 ms 5004 KB 
#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) {
                vector<ll> valMid(m), valR(m), valL(m);
                for (int y = 0; y < m; ++y) {
                    for (int x = x1; x <= x2; ++x) {
                        valMid[y] += diff[15 - (x == x1 ? 1 : 0) - (x == x2 ? 4 : 0)][x][y];
                        valL[y] += diff[15 - 8 - (x == x1 ? 1 : 0) - (x == x2 ? 4 : 0)][x][y];
                        valR[y] += diff[15 - 2 - (x == x1 ? 1 : 0) - (x == x2 ? 4 : 0)][x][y];
                    }
                }
                unordered_map<ll, int> cnt;
                ll prefix = 0;
                for (int y1 = 0; y1 < m; ++y1) {
                    if (y1 > 0) {
                        prefix += valMid[y1 - 1];
                        ++cnt[prefix - valL[y1 - 1]];
                    }
                    ans += cnt[prefix + valR[y1] - (n * m + 1)];
                }
            }
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 8 ms 1280 KB Output is correct
3 Correct 14 ms 1296 KB Output is correct
4 Correct 10 ms 1296 KB Output is correct
5 Correct 11 ms 1272 KB Output is correct
6 Correct 14 ms 1296 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 7 ms 328 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 5 ms 340 KB Output is correct
16 Correct 5 ms 332 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 7 ms 328 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 5 ms 340 KB Output is correct
16 Correct 5 ms 332 KB Output is correct
17 Correct 2 ms 416 KB Output is correct
18 Correct 54 ms 852 KB Output is correct
19 Correct 13 ms 848 KB Output is correct
20 Correct 52 ms 852 KB Output is correct
21 Correct 63 ms 876 KB Output is correct
22 Correct 69 ms 872 KB Output is correct
23 Correct 66 ms 856 KB Output is correct
24 Correct 48 ms 832 KB Output is correct
25 Correct 76 ms 852 KB Output is correct
26 Correct 70 ms 852 KB Output is correct
27 Correct 70 ms 852 KB Output is correct
28 Correct 75 ms 876 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 7 ms 328 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 4 ms 340 KB Output is correct
15 Correct 5 ms 340 KB Output is correct
16 Correct 5 ms 332 KB Output is correct
17 Correct 2 ms 416 KB Output is correct
18 Correct 54 ms 852 KB Output is correct
19 Correct 13 ms 848 KB Output is correct
20 Correct 52 ms 852 KB Output is correct
21 Correct 63 ms 876 KB Output is correct
22 Correct 69 ms 872 KB Output is correct
23 Correct 66 ms 856 KB Output is correct
24 Correct 48 ms 832 KB Output is correct
25 Correct 76 ms 852 KB Output is correct
26 Correct 70 ms 852 KB Output is correct
27 Correct 70 ms 852 KB Output is correct
28 Correct 75 ms 876 KB Output is correct
29 Correct 9 ms 1296 KB Output is correct
30 Correct 341 ms 4312 KB Output is correct
31 Correct 2479 ms 4316 KB Output is correct
32 Correct 19 ms 5004 KB Output is correct
33 Correct 1862 ms 4296 KB Output is correct
34 Correct 2221 ms 4336 KB Output is correct
35 Correct 728 ms 2900 KB Output is correct
36 Correct 1086 ms 4176 KB Output is correct
37 Correct 2572 ms 4176 KB Output is correct
38 Correct 2561 ms 4176 KB Output is correct
39 Correct 2562 ms 4176 KB Output is correct
40 Correct 2586 ms 4176 KB Output is correct
41 Correct 2637 ms 4176 KB Output is correct
42 Correct 2554 ms 4176 KB Output is correct
43 Correct 2596 ms 4168 KB Output is correct
44 Correct 2594 ms 4176 KB Output is correct