Submission #447401

#	Time	Username	Problem	Language	Result	Execution time	Memory
447401		dxz05	Rectangles (IOI19_rect)	C++14	50 / 100	1250 ms	354708 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2550;
const int M = 222;

bool good[M][M][M];

int n, m;
vector<vector<int> > a;

vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};

bool visited[N][N];
int mnx, mny, mxx, mxy, cnt = 0;
void dfs(int x, int y){
    visited[x][y] = true;
    cnt++;

    mnx = min(mnx, x);
    mny = min(mny, y);
    mxx = max(mxx, x);
    mxy = max(mxy, y);

    for (int i = 0; i < 4; i++){
        int X = x + dx[i], Y = y + dy[i];
        if (X > 0 && X < n - 1 && Y > 0 && Y < m - 1 && !visited[X][Y] && a[X][Y] == 0) dfs(X, Y);
    }

}

long long count_rectangles(vector<vector<int> > _a) {
    a = _a;

    n = a.size(), m = a[0].size();
    if (n < 3 || m < 3) return 0;

    if (n == 3) {
        int ans = 0;
        for (int l = 1; l < m - 1; l++) {
            int mx = 0;
            for (int r = l; r < m - 1; r++) {
                mx = max(mx, a[1][r]);
                if (a[1][r] >= min(a[0][r], a[2][r])) break;
                if (mx < min(a[1][l - 1], a[1][r + 1])) ans++;
            }
        }
        return ans;
    }

    if (n <= 200 && m <= 200) {
        for (int i = 1; i < n - 1; i++) {
            for (int x = 1; x < m - 1; x++) {
                int mx = 0;
                for (int y = x; y < m - 1; y++) {
                    mx = max(mx, a[i][y]);
                    if (mx < min(a[i][x - 1], a[i][y + 1])) {
                        //cout << i << ' ' << x << ' ' << y << endl;
                        good[i][x][y] = true;
                    }
                }
            }
        }

        int ans = 0;

        for (int i = 1; i < n - 1; i++) {
            for (int x = 1; x < m - 1; x++) {
                for (int y = x; y < m - 1; y++) {
                    int j = i;
                    vector<int> v(m);
                    while (j < n - 1 && good[j][x][y]) {
                        int cnt = 0;
                        for (int k = x; k <= y; k++) {
                            v[k] = max(v[k], a[j][k]);
                            cnt += v[k] < min(a[i - 1][k], a[j + 1][k]);
                        }

                        if (cnt == y - x + 1) ans++;

                        j++;
                    }
                }
            }
        }

        return ans;
    }

    int ans = 0;
    for (int i = 1; i < n - 1; i++){
        for (int j = 1; j < m - 1; j++){
            if (visited[i][j] || a[i][j] == 1) continue;
            mnx = mny = 1e9, mxx = mxy = cnt = 0;
            dfs(i, j);

            if (cnt != (mxx - mnx + 1) * (mxy - mny + 1)) continue;

            bool ok = true;
            for (int k = mnx; k <= mxx; k++){
                if (a[k][mny - 1] == 0 || a[k][mxy + 1] == 0) ok = false;
            }

            for (int k = mny; k <= mxy; k++){
                if (a[mnx - 1][k] == 0 || a[mxx + 1][k] == 0) ok = false;
            }

            if (ok) ans++;

        }
    }

    return ans;

}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28