QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408874 | #6746. Merge the Rectangles | SanCai | AC ✓ | 31ms | 21596kb | C++14 | 1.3kb | 2024-05-11 10:16:30 | 2024-05-11 10:16:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define sc scanf
#define pt printf
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define ls k+k
#define rs k+k+1
using pll = pair<ll, ll>;
using pii = pair<int, int>;
const int N = 2e5 + 10;
int s1[1510][1510],s2[1510][1510];
bool dfs(int x1,int y1,int x2,int y2)
{
int sum=0;
for(int i=x1+1;i<x2;i++)
{
int s=s1[i][y2]-s1[i][y1];
if(s==y2-y1)
{
if(dfs(x1,y1,i,y2)&&dfs(i,y1,x2,y2))return 1;
else return 0;
}
sum+=s;
}
for(int i=y1+1;i<y2;i++)
{
int s=s2[x2][i]-s2[x1][i];
if(s==x2-x1)
{
if(dfs(x1,y1,x2,i)&&dfs(x1,i,x2,y2))return 1;
else return 0;
}
sum+=s;
}
if(sum)return 0;
else return 1;
}
void UraykevoliQwQ()
{
int n,m;cin>>n>>m;
for(int i=1;i<n;i++)
{
string s;cin>>s;
s=" "+s;
for(int j=1;j<=m;j++)
{
s1[i][j]+=s1[i][j-1]+s[j]-'0';
}
}
for(int i=1;i<=n;i++)
{
string s;cin>>s;
s=" "+s;
for(int j=1;j<m;j++)
{
s2[i][j]+=s2[i-1][j]+s[j]-'0';
}
}
if(dfs(0,0,n,m))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
UraykevoliQwQ();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3536kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 8ms
memory: 21256kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 13ms
memory: 21256kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 3ms
memory: 21280kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 15ms
memory: 21288kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #7:
score: 0
Accepted
time: 9ms
memory: 21256kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #8:
score: 0
Accepted
time: 11ms
memory: 21300kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #9:
score: 0
Accepted
time: 12ms
memory: 21464kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #10:
score: 0
Accepted
time: 12ms
memory: 21428kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #11:
score: 0
Accepted
time: 24ms
memory: 21596kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #12:
score: 0
Accepted
time: 20ms
memory: 21540kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #13:
score: 0
Accepted
time: 10ms
memory: 21240kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #14:
score: 0
Accepted
time: 18ms
memory: 21408kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #15:
score: 0
Accepted
time: 21ms
memory: 21404kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #16:
score: 0
Accepted
time: 21ms
memory: 21296kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #17:
score: 0
Accepted
time: 8ms
memory: 21252kb
input:
1500 1500 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #18:
score: 0
Accepted
time: 15ms
memory: 21400kb
input:
1500 1500 10111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #19:
score: 0
Accepted
time: 29ms
memory: 21404kb
input:
1500 1500 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #20:
score: 0
Accepted
time: 20ms
memory: 21492kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #21:
score: 0
Accepted
time: 6ms
memory: 21292kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #22:
score: 0
Accepted
time: 20ms
memory: 21428kb
input:
1500 1500 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #23:
score: 0
Accepted
time: 21ms
memory: 21428kb
input:
1500 1500 10111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #24:
score: 0
Accepted
time: 14ms
memory: 21256kb
input:
1500 1500 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #25:
score: 0
Accepted
time: 8ms
memory: 21284kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #26:
score: 0
Accepted
time: 25ms
memory: 21432kb
input:
1500 1500 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #27:
score: 0
Accepted
time: 22ms
memory: 21432kb
input:
1500 1500 11011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #28:
score: 0
Accepted
time: 14ms
memory: 21468kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #29:
score: 0
Accepted
time: 14ms
memory: 21488kb
input:
1500 1500 00010000000000011110111101011011110011001110011110011101111011110111000111000110001101111011110101100011011110111101000011110111101110011110000001111011110111101111011100111100110000010110101111011110110000000001100011101111011000011001111011100110001111011110011101111011110111100000011110...
output:
YES
result:
ok answer is YES
Test #30:
score: 0
Accepted
time: 19ms
memory: 21280kb
input:
1500 1500 11100111101111011110000101000011110011101111001000001101111011110111000100011110110100101000000011001110000110111101110011110111101111011110111001000011110110001111001010110000011011110110001111010010111101111011110111000000001110111101111001010111000111000000110000000011000111000001011110...
output:
YES
result:
ok answer is YES
Test #31:
score: 0
Accepted
time: 18ms
memory: 21292kb
input:
1500 1500 11110111101111011110111101111001110000000111011110111101110011100111101101011000111100000000000111101111011110000001110000010111101000011100111101101001100110001111011110100001111011110101101110011000000001110011110111101110001100111101111011110000100000011010111101111011010111101110000000...
output:
YES
result:
ok answer is YES
Test #32:
score: 0
Accepted
time: 15ms
memory: 21240kb
input:
1500 1500 11100000000000000011100000000000000000000001110000000000000000000000000000000000000000000000001110000000000000000000000000001110000000000000000000011100000000111100000011100000011100000000000000000000000000000000000000000011100000000000000000000000001111000000000000000000000000000000000000...
output:
NO
result:
ok answer is NO
Test #33:
score: 0
Accepted
time: 8ms
memory: 21308kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000000000000000000000000000000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #34:
score: 0
Accepted
time: 20ms
memory: 21416kb
input:
1500 1500 00011100000001111000000000000011111100000000000000000000000000000000111000000011100000000001110000111111000000000000000001111000000000000000011110000000000000000000000000000000000000111111001110000000000000001111000000000000000111000000000000000000000000000000111000000000000111000000000000...
output:
YES
result:
ok answer is YES
Test #35:
score: 0
Accepted
time: 3ms
memory: 21436kb
input:
1500 1500 00000000000000000011100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000011110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000...
output:
NO
result:
ok answer is NO
Test #36:
score: 0
Accepted
time: 6ms
memory: 21300kb
input:
1500 1500 00000000011100111100000000000000000000000000000000000000000000000000000111000000000000001110001110000000000001111111101110000000000000000000001111000000011100000000000000000000000000000000000000000011100000111000000000000000001111000000000000000000000000000000000011111000000000000000000000...
output:
NO
result:
ok answer is NO
Test #37:
score: 0
Accepted
time: 12ms
memory: 21244kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000000000000...
output:
YES
result:
ok answer is YES
Test #38:
score: 0
Accepted
time: 17ms
memory: 21248kb
input:
1500 1500 00001110000000000000000011100000000000000000000000000000000111100000000000001111000111000000000000000000000000111000000000000000000000000000000000000000000000000000000000011100000000000000000000000000000111000000000000000000000011100000000011100000000000000001110000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #39:
score: 0
Accepted
time: 6ms
memory: 21316kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000111000000000000000000000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
NO
result:
ok answer is NO
Test #40:
score: 0
Accepted
time: 14ms
memory: 21200kb
input:
1500 1500 00000000000000011100000000000000000000000000000000000000011100000011100000000000000011100011100000000000000000000000000000000000000000000000000000111000000001111000000000000000000000000000001111000001110000000000000000001110000000000000000000000000000000000000001111011100011100000000000000...
output:
NO
result:
ok answer is NO
Test #41:
score: 0
Accepted
time: 14ms
memory: 21312kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #42:
score: 0
Accepted
time: 19ms
memory: 21212kb
input:
1500 1500 00011100000001111111000001111111000011110000000111000000000000011100000000111000000000000000001111000000000000000000000000000000011111000011110000000000000111100000000000001110000000011100001111000000001111000000000001111011110000000000000000000000000000011110000000000000000000000001110000...
output:
YES
result:
ok answer is YES
Test #43:
score: 0
Accepted
time: 7ms
memory: 21488kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
NO
result:
ok answer is NO
Test #44:
score: 0
Accepted
time: 14ms
memory: 21492kb
input:
1500 1500 00001110001110000011110000001111111000000000000111000001110000000000000000000000000000111000000000001110000000011111001111000000000000000000011110000000000111000000001111100000001111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100000...
output:
NO
result:
ok answer is NO
Test #45:
score: 0
Accepted
time: 14ms
memory: 21284kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #46:
score: 0
Accepted
time: 12ms
memory: 21244kb
input:
1500 1500 00000000000000000000000000000000000001110000000000000000000000000000001110000000000000011100000000000000000111100000000000000000001111000000011100000000000000111100000000000000001110000000000000000000111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #47:
score: 0
Accepted
time: 10ms
memory: 21248kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000011100000000000000001110000000000001110000000000000000001110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011100...
output:
NO
result:
ok answer is NO
Test #48:
score: 0
Accepted
time: 5ms
memory: 21280kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #49:
score: 0
Accepted
time: 7ms
memory: 21288kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #50:
score: 0
Accepted
time: 8ms
memory: 14240kb
input:
750 1500 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #51:
score: 0
Accepted
time: 7ms
memory: 21200kb
input:
1500 750 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
NO
result:
ok answer is NO
Test #52:
score: 0
Accepted
time: 8ms
memory: 13400kb
input:
750 1500 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #53:
score: 0
Accepted
time: 10ms
memory: 21272kb
input:
1500 750 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #54:
score: 0
Accepted
time: 12ms
memory: 21256kb
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
YES
result:
ok answer is YES
Test #55:
score: 0
Accepted
time: 24ms
memory: 21468kb
input:
1500 1500 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
output:
YES
result:
ok answer is YES
Test #56:
score: 0
Accepted
time: 25ms
memory: 21496kb
input:
1500 1500 11111111111110110001100000101100100110111111010111111011000111100111111111101111111110011111111111110101111111111111011111111111111111111100001100000001011001011001100001111100110000000000111111111111111111111111111111111111110111111111111111111111111000111111111111000110000011111111100011...
output:
YES
result:
ok answer is YES
Test #57:
score: 0
Accepted
time: 31ms
memory: 21464kb
input:
1500 1500 01101111111000011111111111111111111110011110011101111110000111111001111111111111111111111111111101111011101101111110001101111100001111111111111111111111000001100000110111111111110011001101111111111011100001011111100111101100001111111111111111100001111111111111011111000111111111111111101110...
output:
YES
result:
ok answer is YES