oj.uz

Submission #759226

# Submission time Handle Problem Language Result Execution time Memory
759226 2023-06-15T21:26:58 Z MilosMilutinovic Rectangles (IOI19_rect) C++14
100 / 100
 3526 ms 1014440 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 2525;
int n, m, U[N][N], D[N][N], L[N][N], R[N][N];
vector<pair<int, int>> ver[N], hor[N];
vector<pair<int, int>> my_ver[N][N];
vector<pair<int, int>> my_hor[N][N];

vector<pair<int, int>> clear_vec(vector<pair<int, int>> vec, int x, int y) {
    vector<pair<int, int>> new_vec;
    for (auto& p : vec) {
        if (abs(p.first - x) <= 1 || abs(p.second - y) <= 1) {
            continue;
        }
        new_vec.push_back(p);
    }
    return new_vec;
}

ll count_rectangles(vector<vector<int>> a) {
    n = a.size(), m = a[0].size();

    // find U
    for (int j = 0; j < m; j++) {
        vector<int> stk;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && a[i][j] > a[stk.back()][j]) {
                stk.pop_back();
            }
            U[i][j] = (stk.empty() ? -1 : stk.back());
            stk.push_back(i);
        }
    }

    // find D
    for (int j = 0; j < m; j++) {
        vector<int> stk;
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && a[i][j] > a[stk.back()][j]) {
                stk.pop_back();
            }
            D[i][j] = (stk.empty() ? -1 : stk.back());
            stk.push_back(i);
        }
    }

    // find L
    for (int i = 0; i < n; i++) {
        vector<int> stk;
        for (int j = 0; j < m; j++) {
            while (!stk.empty() && a[i][j] > a[i][stk.back()]) {
                stk.pop_back();
            }
            L[i][j] = (stk.empty() ? -1 : stk.back());
            stk.push_back(j);
        }
    }

    // find R
    for (int i = 0; i < n; i++) {
        vector<int> stk;
        for (int j = m - 1; j >= 0; j--) {
            while (!stk.empty() && a[i][j] > a[i][stk.back()]) {
                stk.pop_back();
            }
            R[i][j] = (stk.empty() ? -1 : stk.back());
            stk.push_back(j);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (R[i][j] != -1 && R[i][j] != j + 1)
                hor[j].emplace_back(R[i][j], i);

            if (L[i][j] != -1 && L[i][j] != j - 1)
                hor[L[i][j]].emplace_back(j, i);

            if (U[i][j] != -1 && U[i][j] != i - 1)
                ver[U[i][j]].emplace_back(i, j);

            if (D[i][j] != -1 && D[i][j] != i + 1)
                ver[i].emplace_back(D[i][j], j);
        }
    }

    for (int j = 0; j < m - 1; j++) {
        sort(hor[j].begin(), hor[j].end());
        hor[j].erase(unique(hor[j].begin(), hor[j].end()), hor[j].end());
        int sz = hor[j].size();
        for (int l = 0; l < sz; l++) {
            int r = l;
            while (r + 1 < sz && hor[j][r + 1].first == hor[j][l].first) r++;
            for (int x = l; x <= r; x++) {
                int y = x;
                while (y + 1 <= r && hor[j][y + 1].second == hor[j][y].second + 1) y++;
                for (int z = x; z <= y; z++) {
                    assert(hor[j][y].first > 0);
                    my_hor[hor[j][z].second][j + 1].emplace_back(hor[j][y].second, hor[j][y].first - 1); // format (i, j)
                }
//                if (hor[j][x].second > 0) {
//                    my_hor[hor[j][x].second - 1][j].emplace_back(min(n - 1, hor[j][y].second + 1), hor[j][y].first); // format (i, j)
//                }
                x = y;
            }
            l = r;
        }
    }

    for (int i = 0; i < n - 1; i++) {
        sort(ver[i].begin(), ver[i].end());
        ver[i].erase(unique(ver[i].begin(), ver[i].end()), ver[i].end());
        int sz = ver[i].size();
        for (int l = 0; l < sz; l++) {
            int r = l;
            while (r + 1 < sz && ver[i][r + 1].first == ver[i][l].first) r++;
            for (int x = l; x <= r; x++) {
                int y = x;
                while (y + 1 <= r && ver[i][y + 1].second == ver[i][y].second + 1) y++;
                for (int z = x; z <= y; z++) {
                    assert(ver[i][y].first > 0);
                    my_ver[i + 1][ver[i][z].second].emplace_back(ver[i][y].first - 1, ver[i][y].second); // format (i, j)
                }
//                if (ver[i][x].second > 0) {
//                    my_ver[i][ver[i][x].second - 1].emplace_back(ver[i][y].first, min(m - 1, ver[i][y].second + 1)); // format (i, j)
//                }
                x = y;
            }
            l = r;
        }
    }

//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            printf("(%d, %d): ", i, j);
//            for (auto& p : my_ver[i][j]) {
//                printf("[%d, %d] ", p.first, p.second);
//            }
//            printf("\n");
//        }
//    }
//
//    printf("\n");
//    printf("\n");
//    printf("\n");
//    printf("\n");
//    printf("\n");
//
//    for (int i = 0; i < n; i++) {
//        for (int j = 0; j < m; j++) {
//            printf("(%d, %d): ", i, j);
//            for (auto& p : my_hor[i][j]) {
//                printf("[%d, %d] ", p.first, p.second);
//            }
//            printf("\n");
//        }
//    }

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m - 1; j++) {
            sort(my_hor[i][j].begin(), my_hor[i][j].end());
//            my_hor[i][j] = clear_vec(my_hor[i][j], i, j);
            my_hor[i][j].erase(unique(my_hor[i][j].begin(), my_hor[i][j].end()), my_hor[i][j].end());


            sort(my_ver[i][j].begin(), my_ver[i][j].end());
//            my_ver[i][j] = clear_vec(my_ver[i][j], i, j);
            my_ver[i][j].erase(unique(my_ver[i][j].begin(), my_ver[i][j].end()), my_ver[i][j].end());
        }
    }

    auto is_valid = [&](int l1, int r1, int l2, int r2) {
        assert(l1 > 0 && l1 <= l2 && l2 < n - 1 && r1 > 0 && r1 <= r2 && r2 < m - 1);
        for (int i = l1; i <= l2; i++) {
            for (int j = r1; j <= r2; j++) {
                if (a[i][j] >= a[l1 - 1][j]) return false;
                if (a[i][j] >= a[l2 + 1][j]) return false;
                if (a[i][j] >= a[i][r1 - 1]) return false;
                if (a[i][j] >= a[i][r2 + 1]) return false;
            }
        }
        return true;
    };

    ll ans = 0;
    for (int i = 1; i < n - 1; i++) {
        for (int j = 1; j < m - 1; j++) {
            vector<pair<int, int>> cells;
            for (auto& r : my_hor[i][j]) {
                for (auto& b : my_ver[i][j]) {
                    if (b.first <= r.first && b.second >= r.second) {
                        cells.emplace_back(b.first, r.second);
                    }
                }
            }
            sort(cells.begin(), cells.end());
            cells.erase(unique(cells.begin(), cells.end()), cells.end());
            for (auto& ff : cells) {
//                if (is_valid(i, j, ff.first, ff.second))
                    ans++;
            }
        }
    }


    return ans;
}

/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:202:24: warning: unused variable 'ff' [-Wunused-variable]
  202 |             for (auto& ff : cells) {
      |                        ^~
rect.cpp:176:10: warning: variable 'is_valid' set but not used [-Wunused-but-set-variable]
  176 |     auto is_valid = [&](int l1, int r1, int l2, int r2) {
      |          ^~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 299928 KB Output is correct
2 Correct 127 ms 300424 KB Output is correct
3 Correct 123 ms 300372 KB Output is correct
4 Correct 136 ms 300360 KB Output is correct
5 Correct 136 ms 300252 KB Output is correct
6 Correct 123 ms 300364 KB Output is correct
7 Correct 128 ms 300320 KB Output is correct
8 Correct 124 ms 300056 KB Output is correct
9 Correct 124 ms 300368 KB Output is correct
10 Correct 123 ms 300312 KB Output is correct
11 Correct 133 ms 300344 KB Output is correct
12 Correct 125 ms 300404 KB Output is correct
13 Correct 123 ms 299860 KB Output is correct
14 Correct 124 ms 299940 KB Output is correct
15 Correct 127 ms 299912 KB Output is correct
16 Correct 127 ms 299844 KB Output is correct
17 Correct 124 ms 299840 KB Output is correct
18 Correct 125 ms 299756 KB Output is correct
19 Correct 127 ms 300316 KB Output is correct
20 Correct 129 ms 300504 KB Output is correct
21 Correct 128 ms 299920 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 299928 KB Output is correct
2 Correct 127 ms 300424 KB Output is correct
3 Correct 123 ms 300372 KB Output is correct
4 Correct 136 ms 300360 KB Output is correct
5 Correct 136 ms 300252 KB Output is correct
6 Correct 123 ms 300364 KB Output is correct
7 Correct 128 ms 300320 KB Output is correct
8 Correct 124 ms 300056 KB Output is correct
9 Correct 124 ms 300368 KB Output is correct
10 Correct 123 ms 300312 KB Output is correct
11 Correct 133 ms 300344 KB Output is correct
12 Correct 125 ms 300404 KB Output is correct
13 Correct 123 ms 299860 KB Output is correct
14 Correct 124 ms 299940 KB Output is correct
15 Correct 127 ms 299912 KB Output is correct
16 Correct 127 ms 299844 KB Output is correct
17 Correct 124 ms 299840 KB Output is correct
18 Correct 125 ms 299756 KB Output is correct
19 Correct 127 ms 300316 KB Output is correct
20 Correct 129 ms 300504 KB Output is correct
21 Correct 128 ms 299920 KB Output is correct
22 Correct 126 ms 301772 KB Output is correct
23 Correct 125 ms 301900 KB Output is correct
24 Correct 132 ms 301988 KB Output is correct
25 Correct 128 ms 301500 KB Output is correct
26 Correct 129 ms 301596 KB Output is correct
27 Correct 131 ms 301616 KB Output is correct
28 Correct 129 ms 301648 KB Output is correct
29 Correct 124 ms 301340 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 299928 KB Output is correct
2 Correct 127 ms 300424 KB Output is correct
3 Correct 123 ms 300372 KB Output is correct
4 Correct 136 ms 300360 KB Output is correct
5 Correct 136 ms 300252 KB Output is correct
6 Correct 123 ms 300364 KB Output is correct
7 Correct 128 ms 300320 KB Output is correct
8 Correct 124 ms 300056 KB Output is correct
9 Correct 124 ms 300368 KB Output is correct
10 Correct 123 ms 300312 KB Output is correct
11 Correct 133 ms 300344 KB Output is correct
12 Correct 125 ms 300404 KB Output is correct
13 Correct 123 ms 299860 KB Output is correct
14 Correct 124 ms 299940 KB Output is correct
15 Correct 127 ms 299912 KB Output is correct
16 Correct 127 ms 299844 KB Output is correct
17 Correct 126 ms 301772 KB Output is correct
18 Correct 125 ms 301900 KB Output is correct
19 Correct 132 ms 301988 KB Output is correct
20 Correct 128 ms 301500 KB Output is correct
21 Correct 129 ms 301596 KB Output is correct
22 Correct 131 ms 301616 KB Output is correct
23 Correct 129 ms 301648 KB Output is correct
24 Correct 124 ms 301340 KB Output is correct
25 Correct 124 ms 299840 KB Output is correct
26 Correct 125 ms 299756 KB Output is correct
27 Correct 127 ms 300316 KB Output is correct
28 Correct 129 ms 300504 KB Output is correct
29 Correct 128 ms 299920 KB Output is correct
30 Correct 134 ms 307520 KB Output is correct
31 Correct 135 ms 307428 KB Output is correct
32 Correct 152 ms 307568 KB Output is correct
33 Correct 134 ms 305524 KB Output is correct
34 Correct 139 ms 306340 KB Output is correct
35 Correct 140 ms 306544 KB Output is correct
36 Correct 139 ms 306384 KB Output is correct
37 Correct 144 ms 306348 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 299928 KB Output is correct
2 Correct 127 ms 300424 KB Output is correct
3 Correct 123 ms 300372 KB Output is correct
4 Correct 136 ms 300360 KB Output is correct
5 Correct 136 ms 300252 KB Output is correct
6 Correct 123 ms 300364 KB Output is correct
7 Correct 128 ms 300320 KB Output is correct
8 Correct 124 ms 300056 KB Output is correct
9 Correct 124 ms 300368 KB Output is correct
10 Correct 123 ms 300312 KB Output is correct
11 Correct 133 ms 300344 KB Output is correct
12 Correct 125 ms 300404 KB Output is correct
13 Correct 123 ms 299860 KB Output is correct
14 Correct 124 ms 299940 KB Output is correct
15 Correct 127 ms 299912 KB Output is correct
16 Correct 127 ms 299844 KB Output is correct
17 Correct 126 ms 301772 KB Output is correct
18 Correct 125 ms 301900 KB Output is correct
19 Correct 132 ms 301988 KB Output is correct
20 Correct 128 ms 301500 KB Output is correct
21 Correct 129 ms 301596 KB Output is correct
22 Correct 131 ms 301616 KB Output is correct
23 Correct 129 ms 301648 KB Output is correct
24 Correct 124 ms 301340 KB Output is correct
25 Correct 134 ms 307520 KB Output is correct
26 Correct 135 ms 307428 KB Output is correct
27 Correct 152 ms 307568 KB Output is correct
28 Correct 134 ms 305524 KB Output is correct
29 Correct 139 ms 306340 KB Output is correct
30 Correct 140 ms 306544 KB Output is correct
31 Correct 139 ms 306384 KB Output is correct
32 Correct 144 ms 306348 KB Output is correct
33 Correct 124 ms 299840 KB Output is correct
34 Correct 125 ms 299756 KB Output is correct
35 Correct 127 ms 300316 KB Output is correct
36 Correct 129 ms 300504 KB Output is correct
37 Correct 128 ms 299920 KB Output is correct
38 Correct 203 ms 346740 KB Output is correct
39 Correct 186 ms 341964 KB Output is correct
40 Correct 202 ms 341964 KB Output is correct
41 Correct 219 ms 337248 KB Output is correct
42 Correct 248 ms 367632 KB Output is correct
43 Correct 250 ms 367668 KB Output is correct
44 Correct 255 ms 367968 KB Output is correct
45 Correct 247 ms 363956 KB Output is correct
46 Correct 220 ms 336816 KB Output is correct
47 Correct 251 ms 339572 KB Output is correct
48 Correct 348 ms 353488 KB Output is correct
49 Correct 347 ms 355552 KB Output is correct
50 Correct 237 ms 333400 KB Output is correct
51 Correct 232 ms 327672 KB Output is correct
52 Correct 321 ms 352440 KB Output is correct
53 Correct 333 ms 353368 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 300528 KB Output is correct
2 Correct 124 ms 300356 KB Output is correct
3 Correct 127 ms 300072 KB Output is correct
4 Correct 136 ms 299816 KB Output is correct
5 Correct 126 ms 300300 KB Output is correct
6 Correct 128 ms 300356 KB Output is correct
7 Correct 128 ms 300312 KB Output is correct
8 Correct 126 ms 300236 KB Output is correct
9 Correct 129 ms 300324 KB Output is correct
10 Correct 124 ms 299980 KB Output is correct
11 Correct 124 ms 300156 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 299840 KB Output is correct
2 Correct 125 ms 299756 KB Output is correct
3 Correct 127 ms 300316 KB Output is correct
4 Correct 129 ms 300504 KB Output is correct
5 Correct 128 ms 299920 KB Output is correct
6 Correct 128 ms 299928 KB Output is correct
7 Correct 758 ms 451904 KB Output is correct
8 Correct 1622 ms 617400 KB Output is correct
9 Correct 1548 ms 619592 KB Output is correct
10 Correct 1521 ms 619432 KB Output is correct
11 Correct 303 ms 375528 KB Output is correct
12 Correct 541 ms 447292 KB Output is correct
13 Correct 572 ms 450400 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 299928 KB Output is correct
2 Correct 127 ms 300424 KB Output is correct
3 Correct 123 ms 300372 KB Output is correct
4 Correct 136 ms 300360 KB Output is correct
5 Correct 136 ms 300252 KB Output is correct
6 Correct 123 ms 300364 KB Output is correct
7 Correct 128 ms 300320 KB Output is correct
8 Correct 124 ms 300056 KB Output is correct
9 Correct 124 ms 300368 KB Output is correct
10 Correct 123 ms 300312 KB Output is correct
11 Correct 133 ms 300344 KB Output is correct
12 Correct 125 ms 300404 KB Output is correct
13 Correct 123 ms 299860 KB Output is correct
14 Correct 124 ms 299940 KB Output is correct
15 Correct 127 ms 299912 KB Output is correct
16 Correct 127 ms 299844 KB Output is correct
17 Correct 126 ms 301772 KB Output is correct
18 Correct 125 ms 301900 KB Output is correct
19 Correct 132 ms 301988 KB Output is correct
20 Correct 128 ms 301500 KB Output is correct
21 Correct 129 ms 301596 KB Output is correct
22 Correct 131 ms 301616 KB Output is correct
23 Correct 129 ms 301648 KB Output is correct
24 Correct 124 ms 301340 KB Output is correct
25 Correct 134 ms 307520 KB Output is correct
26 Correct 135 ms 307428 KB Output is correct
27 Correct 152 ms 307568 KB Output is correct
28 Correct 134 ms 305524 KB Output is correct
29 Correct 139 ms 306340 KB Output is correct
30 Correct 140 ms 306544 KB Output is correct
31 Correct 139 ms 306384 KB Output is correct
32 Correct 144 ms 306348 KB Output is correct
33 Correct 203 ms 346740 KB Output is correct
34 Correct 186 ms 341964 KB Output is correct
35 Correct 202 ms 341964 KB Output is correct
36 Correct 219 ms 337248 KB Output is correct
37 Correct 248 ms 367632 KB Output is correct
38 Correct 250 ms 367668 KB Output is correct
39 Correct 255 ms 367968 KB Output is correct
40 Correct 247 ms 363956 KB Output is correct
41 Correct 220 ms 336816 KB Output is correct
42 Correct 251 ms 339572 KB Output is correct
43 Correct 348 ms 353488 KB Output is correct
44 Correct 347 ms 355552 KB Output is correct
45 Correct 237 ms 333400 KB Output is correct
46 Correct 232 ms 327672 KB Output is correct
47 Correct 321 ms 352440 KB Output is correct
48 Correct 333 ms 353368 KB Output is correct
49 Correct 125 ms 300528 KB Output is correct
50 Correct 124 ms 300356 KB Output is correct
51 Correct 127 ms 300072 KB Output is correct
52 Correct 136 ms 299816 KB Output is correct
53 Correct 126 ms 300300 KB Output is correct
54 Correct 128 ms 300356 KB Output is correct
55 Correct 128 ms 300312 KB Output is correct
56 Correct 126 ms 300236 KB Output is correct
57 Correct 129 ms 300324 KB Output is correct
58 Correct 124 ms 299980 KB Output is correct
59 Correct 124 ms 300156 KB Output is correct
60 Correct 128 ms 299928 KB Output is correct
61 Correct 758 ms 451904 KB Output is correct
62 Correct 1622 ms 617400 KB Output is correct
63 Correct 1548 ms 619592 KB Output is correct
64 Correct 1521 ms 619432 KB Output is correct
65 Correct 303 ms 375528 KB Output is correct
66 Correct 541 ms 447292 KB Output is correct
67 Correct 572 ms 450400 KB Output is correct
68 Correct 124 ms 299840 KB Output is correct
69 Correct 125 ms 299756 KB Output is correct
70 Correct 127 ms 300316 KB Output is correct
71 Correct 129 ms 300504 KB Output is correct
72 Correct 128 ms 299920 KB Output is correct
73 Correct 1389 ms 752416 KB Output is correct
74 Correct 1020 ms 684472 KB Output is correct
75 Correct 1378 ms 688500 KB Output is correct
76 Correct 2627 ms 618800 KB Output is correct
77 Correct 3492 ms 1011540 KB Output is correct
78 Correct 2092 ms 615684 KB Output is correct
79 Correct 2211 ms 680088 KB Output is correct
80 Correct 3419 ms 827664 KB Output is correct
81 Correct 2097 ms 631664 KB Output is correct
82 Correct 2848 ms 758124 KB Output is correct
83 Correct 3526 ms 855364 KB Output is correct
84 Correct 1915 ms 609132 KB Output is correct
85 Correct 3232 ms 825444 KB Output is correct
86 Correct 3148 ms 807712 KB Output is correct
87 Correct 1641 ms 772228 KB Output is correct
88 Correct 3266 ms 1012492 KB Output is correct
89 Correct 2934 ms 1014372 KB Output is correct
90 Correct 3048 ms 1014440 KB Output is correct