oj.uz

Submission #1055228

# Submission time Handle Problem Language Result Execution time Memory
1055228 2024-08-12T15:43:51 Z RecursiveCo Rectangles (IOI19_rect) C++17
23 / 100
 217 ms 122964 KB 
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> pref;

int query(int r1, int c1, int r2, int c2) {
    int val = pref[r2][c2];
    val -= (c1? pref[r2][c1 - 1]: 0);
    val -= (r1? pref[r1 - 1][c2]: 0);
    val += (c1 && r1? pref[r1 - 1][c1 - 1]: 0);
    return val;
}

long long count_rectangles(vector<vector<int>> grid) {
    int n = grid.size();
    int m = grid[0].size();
    int maxi = -1;
    for (int i = 0; i < n; i++) maxi = max(maxi, *max_element(grid[i].begin(), grid[i].end()));
    if (maxi <= 1) {
        // Subtask 6
        pref.resize(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            int prefhere = 0;
            for (int j = 0; j < m; j++) {
                prefhere += grid[i][j];
                pref[i][j] = (i? pref[i - 1][j]: 0) + prefhere;
            }
        }
        vector<vector<int>> left(n, vector<int>(m, -1));
        vector<vector<int>> above(n, vector<int>(m, -1));
        for (int i = 0; i < n; i++) {
            int here = -1;
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) here = j;
                left[i][j] = here;
            }
        }
        for (int j = 0; j < m; j++) {
            int here = -1;
            for (int i = 0; i < n; i++) {
                if (grid[i][j]) here = i;
                above[i][j] = here;
            }
        }
        long long ans = 0;
        for (int i = 1; i < n - 1; i++) {
            for (int j = 1; j < m - 1; j++) {
                if (!grid[i][j] && grid[i + 1][j] && grid[i][j + 1] && left[i][j] != -1 && above[i][j] != -1) {
                    int l = left[i][j];
                    int t = above[i][j];
                    int bottom = query(i + 1, l + 1, i + 1, j);
                    int top = query(t, l + 1, t, j);
                    int leftside = query(t + 1, l, i, l);
                    int rightside = query(t + 1, j + 1, i, j + 1);
                    int inside = query(t + 1, l + 1, i, j);
                    if (bottom == j - l && top == j - l && leftside == i - t && rightside == i - t && !inside) ans++;
                }
            }
        }
        return ans;
    } else if (n == 3) {
        long long ans = 0;
        for (int j = 1; j < m - 1; j++) {
            int maxi = -1;
            for (int k = j; k < m - 1; k++) {
                if (grid[1][k] >= min(grid[0][k], grid[2][k])) break;
                maxi = max(maxi, grid[1][k]);
                if (maxi < min(grid[1][j - 1], grid[1][k + 1])) ans++;
            }
        }
        return ans;
    } else if (max(n, m) <= 30) {
        long long ans = 0;
        for (int j = 1; j < m - 1; j++) {
            for (int k = j; k < m - 1; k++) {
                for (int i = 1; i < n - 1; i++) {
                    vector<int> maxi(k - j + 1, -1);
                    for (int r = i; r < n - 1; r++) {
                        bool here = true;
                        for (int l = j; l <= k; l++) {
                            if (grid[r][l] >= min(grid[r][j - 1], grid[r][k + 1])) here = false;
                            maxi[l - j] = max(maxi[l - j], grid[i][l]);
                        }
                        if (!here) break;
                        for (int l = j; l <= k; l++) {
                            if (maxi[l - j] >= min(grid[i - 1][l], grid[r + 1][l])) here = false;
                        }
                        if (here) ans++;
                    }
                }
            }
        }
        return ans;
    }
    return 0; // for subtasks I'm not solving. (or n is 1 or 2)
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 76 ms 56660 KB Output is correct
3 Correct 171 ms 122392 KB Output is correct
4 Correct 217 ms 122964 KB Output is correct
5 Correct 168 ms 122960 KB Output is correct
6 Correct 60 ms 61012 KB Output is correct
7 Correct 118 ms 115536 KB Output is correct
8 Correct 126 ms 122960 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -