Submission #1055239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055239		RecursiveCo	Rectangles (IOI19_rect)	C++17	31 / 100	191 ms	123212 KiB

rect

#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[r][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: 8 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28