Submission #147149

#	Time	Username	Problem	Language	Result	Execution time	Memory
147149		Mamnoon_Siam	Rectangles (IOI19_rect)	C++17	72 / 100	5108 ms	310276 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

namespace binary_grid {
	const int inf = 1e5;
	const int maxn = 2501;
	int dx[] = {+1, 0, -1, 0};
	int dy[] = {0, -1, 0, +1};
	 
	int n, m;
	int a[maxn][maxn];
	int vis[maxn][maxn];
	 
	int cnt = 0;
	int mnx, mxx, mny, mxy;
	void dfs(int x, int y) {
		cnt++;
	 
		vis[x][y] = 1;
	 
		mnx = min(mnx, x);
		mxx = max(mxx, x);
		mny = min(mny, y);
		mxy = max(mxy, y);
	 
		for(int i = 0; i < 4; i++) {
			int xx = dx[i] + x;
			int yy = dy[i] + y;
			if(1 <= xx and xx <= n and 1 <= yy and yy <= m and a[xx][yy] == 0 and !vis[xx][yy]) {
				dfs(xx, yy);
			}
		}
	}
	 
	int count_rectangles(vector<vector<int> > aa) {
		n = aa.size(), m = aa[0].size();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				a[i + 1][j + 1] = aa[i][j];
			}
		}
		int ans = 0;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				if(!vis[i][j] and a[i][j] == 0) {
					mnx = inf, mxx = -inf;
					mny = inf, mxy = -inf;
					cnt = 0;
					dfs(i, j);
					if((mxx - mnx + 1) * (mxy - mny + 1) == cnt and mnx != 1 and mxx != n and mny != 1 and mxy != m) {
						ans++;
					}
				}
			}
		} return ans;
	}
}

namespace slow_general {
	using ii = pair<int, int>;
	using ll = long long;
	const int N = 2500;
	const int inf = 1e9;

	int n, m;
	int g[N][N];
	bitset<N> ls[N][N];
	int mxx[N];

	int count_rectangles(vector<vector<int> > a) {
		n = a.size(), m = a[0].size();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				g[i][j] = a[i][j];
			}
		}
		for(int i = 1; i < n - 1; i++) {
			for(int j = 1; j < m - 1; j++) {
				int mx = -inf;
				for(int k = j; k > 0; k--) {
					mx = max(mx, g[i][k]);
					if(mx < g[i][j + 1]) {
						if(mx < g[i][k - 1]) {
							ls[i][j][k] = 1;
						}
					} else {
						break;
					}
				}
			}
		}
		int ans = 0;
		for(int u = 1; u < n - 1; u++) {
			for(int i = 1; i < m - 1; i++) {
				mxx[i] = -inf;
			}
			for(int v = u; v < n - 1; v++) {
				bitset<N> can;
				for(int i = 1; i < m - 1; i++) {
					mxx[i] = max(mxx[i], g[v][i]);
					if(mxx[i] < g[u - 1][i] and mxx[i] < g[v + 1][i]) {
						can[i] = 1;
					}
				}
				int now = 0;
				while(can._Find_next(now) < m - 1) {
					int l = can._Find_next(now);
					int r = l;
					while(can[r + 1]) {
						r++;
					}
					bitset<N> range;
					for(int i = l; i <= r; i++) {
						range[i] = 1;
					}
					for(int j = l; j <= r; j++) {
						bitset<N> intersection = range;
						for(int i = u; i <= v; i++) {
							intersection &= ls[i][j];
							if(intersection.count() == 0) {
								break;
							}
						}
						ans += intersection.count();
					}
					now = r;
				}
			}
			move_u : ;
		}
		return ans;
	}
}

long long count_rectangles(vector<vector<int> > a) {
	int n = a.size(), m = a[0].size();
	int mx = -1e9, mn = 1e9;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			mx = max(mx, a[i][j]);
			mn = min(mn, a[i][j]);
		}
	}
	if(0 <= mn and mx <= 1) {
		return binary_grid::count_rectangles(a);
	} else {
		return slow_general::count_rectangles(a);
	}
}

Compilation message (stderr)

rect.cpp: In function 'int slow_general::count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:107:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(can._Find_next(now) < m - 1) {
           ~~~~~~~~~~~~~~~~~~~~^~~~~~~
rect.cpp:130:4: warning: label 'move_u' defined but not used [-Wunused-label]
    move_u : ;
    ^~~~~~

• 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