oj.uz

Submission #941459

# Submission time Handle Problem Language Result Execution time Memory
941459 2024-03-09T01:18:22 Z peterandvoi Sandcastle 2 (JOI22_ho_t5) C++17
100 / 100
 373 ms 17588 KB 
// 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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 109 ms 17188 KB Output is correct
3 Correct 114 ms 16652 KB Output is correct
4 Correct 116 ms 17124 KB Output is correct
5 Correct 116 ms 17192 KB Output is correct
6 Correct 116 ms 17184 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 3 ms 600 KB Output is correct
16 Correct 2 ms 604 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 3 ms 600 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 4 ms 2648 KB Output is correct
18 Correct 12 ms 1372 KB Output is correct
19 Correct 6 ms 1568 KB Output is correct
20 Correct 17 ms 1372 KB Output is correct
21 Correct 16 ms 1372 KB Output is correct
22 Correct 19 ms 1372 KB Output is correct
23 Correct 19 ms 1528 KB Output is correct
24 Correct 19 ms 1372 KB Output is correct
25 Correct 19 ms 1572 KB Output is correct
26 Correct 18 ms 1624 KB Output is correct
27 Correct 17 ms 1372 KB Output is correct
28 Correct 18 ms 1372 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 3 ms 600 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 4 ms 2648 KB Output is correct
18 Correct 12 ms 1372 KB Output is correct
19 Correct 6 ms 1568 KB Output is correct
20 Correct 17 ms 1372 KB Output is correct
21 Correct 16 ms 1372 KB Output is correct
22 Correct 19 ms 1372 KB Output is correct
23 Correct 19 ms 1528 KB Output is correct
24 Correct 19 ms 1372 KB Output is correct
25 Correct 19 ms 1572 KB Output is correct
26 Correct 18 ms 1624 KB Output is correct
27 Correct 17 ms 1372 KB Output is correct
28 Correct 18 ms 1372 KB Output is correct
29 Correct 113 ms 17588 KB Output is correct
30 Correct 84 ms 8064 KB Output is correct
31 Correct 255 ms 8044 KB Output is correct
32 Correct 115 ms 12712 KB Output is correct
33 Correct 291 ms 7892 KB Output is correct
34 Correct 274 ms 7896 KB Output is correct
35 Correct 193 ms 5404 KB Output is correct
36 Correct 299 ms 7888 KB Output is correct
37 Correct 370 ms 7992 KB Output is correct
38 Correct 373 ms 7996 KB Output is correct
39 Correct 327 ms 7896 KB Output is correct
40 Correct 361 ms 7992 KB Output is correct
41 Correct 322 ms 7988 KB Output is correct
42 Correct 326 ms 7896 KB Output is correct
43 Correct 317 ms 7988 KB Output is correct
44 Correct 329 ms 7896 KB Output is correct