제출 #810940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810940		dxz05	Rectangles (IOI19_rect)	C++17	72 / 100	2773 ms	366152 KiB

rect

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

using namespace std;

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

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

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

    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);
    }

}

const int MaxN = 702;

bool good[MaxN][MaxN][MaxN]; // i, l, r -> l..r subarray of i
vector<int> val[MaxN][MaxN];

int cnt[MaxN * MaxN];

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

	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 (max(n, m) <= 700){
		for (int i = 1; i + 1 < n; i++){
			for (int l = 0; l + 2 < m; l++){
				int mx = A[i][l + 1];
				for (int r = l + 2; r < m; r++){
					if (A[i][l] > mx && A[i][r] > mx){
						good[i][l][r] = true;
					}
					mx = max(mx, A[i][r]);
				}
			}
		}

		for (int j = 0; j < m; j++){
			for (int l = 0; l + 2 < n; l++){
				int mx = A[l + 1][j];
				for (int r = l + 2; r < n; r++){
					if (A[l][j] > mx && A[r][j] > mx){
						val[r][j].push_back(l * n + r);
					}
					mx = max(mx, A[r][j]);
				}
			}
		}

		int ans = 0;
		for (int l = 0; l + 2 < m; l++) for (int r = l + 2; r < m; r++){
			for (int x = 0; x + 2 < n; x++){
				if (!good[x + 1][l][r] || good[x][l][r]) continue;

				vector<int> used_values;

				for (int y = x + 2; y < n; y++){
					for (int j = l + 1; j < r; j++){
						for (int v : val[y][j]){
							if (v / n < x) continue;
							cnt[v]++;
							if (cnt[v] == r - l - 1) ans++;
							used_values.push_back(v);
						}
					}
					if (!good[y][l][r]) break;
				}

				for (int v : used_values){
					cnt[v] = 0;
				}

			}
		}

		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 = ver = 0;
            dfs(i, j);

            if (ver != (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: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28