QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#411768 | #6746. Merge the Rectangles | Ynoiynoi# | RE | 0ms | 9928kb | C++17 | 2.3kb | 2024-05-15 19:19:10 | 2024-05-15 19:19:11 |
Judging History
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...