QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#411768#6746. Merge the RectanglesYnoiynoi#RE 0ms9928kbC++172.3kb2024-05-15 19:19:102024-05-15 19:19:11

Judging History

你现在查看的是最新测评结果

  • [2024-05-15 19:19:11]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:9928kb
  • [2024-05-15 19:19:10]
  • 提交

answer

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

#define MAXN 1005

int n,m;
int LG[MAXN];
struct ST {
	int nn;
	int a[MAXN];
	int f[MAXN][12];
	void init(int n) {
		for(int i = 1; i <= n; i ++)
			f[i][0] = a[i];
		for(int j = 1; j <= 11; j ++)
			for(int i = 1; i <= n; i ++)
				f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}

	int rmq(int l,int r) {
		int o = LG[r-l+1];
		return max(f[l][o],f[r-(1<<o)+1][o]);
	}
}c[MAXN],d[MAXN];

char a[MAXN][MAXN],b[MAXN][MAXN];
int sa[MAXN][MAXN],sb[MAXN][MAXN];

bool clr(int x1,int y1,int x2,int y2) {
	return sb[x2][y2-1]-sb[x1-1][y2-1]-sb[x2][y1-1]+sb[x1-1][y1-1] == 0
		&& sa[x2-1][y2]-sa[x1-1][y2]-sa[x2-1][y1-1]+sa[x1-1][y1-1] == 0;
}

bool qwq(int x1,int x2,int y1,int y2) {
//	cout<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<"\n";
	if(clr(x1,y1,x2,y2)) return 1;
	int l = x1,r = x2-1,t = 0;
	while(l+3 < r) {
		int mid = (l+r)>>1;
		if(c[y2].rmq(x1,mid) >= y2-y1+1) r = mid;
		else l = mid;
	}
	for(int i = l; i <= r; i ++)
	if(c[y2].rmq(x1,i) >= y2-y1+1) {
		t = i;
		break;
	}
	if(t) return qwq(x1,t,y1,y2) && qwq(t+1,x2,y1,y2);

	l = y1; r = y2-1;
	while(l+3 < r) {
		int mid = (l+r)>>1;
		if(d[x2].rmq(y1,mid) >= x2-x1+1) r = mid;
		else l = mid;
	}
//	cout<<l<<" "<<r<<"?\n";
	for(int i = l; i <= r; i ++)
	if(d[x2].rmq(y1,i) >= x2-x1+1) {
		t = i;
		break;
	}

	if(t) return qwq(x1,x2,y1,t) && qwq(x1,x2,t+1,y2);
	return 0;
}

signed main() {
	cin >> n >> m;
	for(int i = 1; i < n; i ++)
		scanf("%s",a[i]+1);
	for(int i = 1; i <= n; i ++)
		scanf("%s",b[i]+1);
	for(int i = 2; i <= max(n,m); i ++)
		LG[i] = LG[i>>1]+1;
	for(int i = 1; i < n; i ++)
		for(int j = 1; j <= m; j ++) {
			if(a[i][j] == '0') c[j].a[i] = 0;
			else c[j].a[i] = c[j-1].a[i]+1;
			sa[i][j] = a[i][j]-'0'+sa[i-1][j]+sa[i][j-1]-sa[i-1][j-1];
		}
	for(int j = 1; j <= m; j ++)
		c[j].init(n-1);

	for(int i = 1; i <= n; i ++)
		for(int j = 1; j < m; j ++) {
			if(b[i][j] == '0') d[i].a[j] = 0;
			else d[i].a[j] = d[i-1].a[j]+1;
			sb[i][j] = b[i][j]-'0'+sb[i-1][j]+sb[i][j-1]-sb[i-1][j-1];
		}
	for(int i = 1; i <= n; i ++) {
		d[i].init(m-1);
		/*for(int j = 1; j <= m; j ++)
			cout<<d[i].a[j]<<" ";
		cout<<"\n";
		cout<<d[i].rmq(1,m)<<"\n";*/
	}
	if(qwq(1,n,1,m)) cout<<"YES\n";
	else cout<<"NO\n";
	return 0;
}
/*
3 4
0000
0111
101
101
110

3 3
110
011
01
11
10
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7892kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 0ms
memory: 9928kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: -100
Runtime Error

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:


result: