oj.uz

Submission #594553

# Submission time Handle Problem Language Result Execution time Memory
594553 2022-07-12T16:38:30 Z piOOE Sandcastle 2 (JOI22_ho_t5) C++17
24 / 100
 5000 ms 1296 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) {
                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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 9 ms 1296 KB Output is correct
3 Correct 14 ms 1292 KB Output is correct
4 Correct 11 ms 1296 KB Output is correct
5 Correct 14 ms 1296 KB Output is correct
6 Correct 17 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 212 KB Output is correct
3 Correct 1 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 324 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 212 KB Output is correct
3 Correct 1 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 324 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 204 ms 424 KB Output is correct
10 Correct 193 ms 428 KB Output is correct
11 Correct 217 ms 428 KB Output is correct
12 Correct 214 ms 464 KB Output is correct
13 Correct 179 ms 424 KB Output is correct
14 Correct 64 ms 340 KB Output is correct
15 Correct 192 ms 420 KB Output is correct
16 Correct 196 ms 424 KB Output is correct

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 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 324 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 204 ms 424 KB Output is correct
10 Correct 193 ms 428 KB Output is correct
11 Correct 217 ms 428 KB Output is correct
12 Correct 214 ms 464 KB Output is correct
13 Correct 179 ms 424 KB Output is correct
14 Correct 64 ms 340 KB Output is correct
15 Correct 192 ms 420 KB Output is correct
16 Correct 196 ms 424 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Execution timed out 5042 ms 840 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 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 324 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 204 ms 424 KB Output is correct
10 Correct 193 ms 428 KB Output is correct
11 Correct 217 ms 428 KB Output is correct
12 Correct 214 ms 464 KB Output is correct
13 Correct 179 ms 424 KB Output is correct
14 Correct 64 ms 340 KB Output is correct
15 Correct 192 ms 420 KB Output is correct
16 Correct 196 ms 424 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Execution timed out 5042 ms 840 KB Time limit exceeded
19 Halted 0 ms 0 KB -