#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=1007;
const ll LG=25;
ll n,m,k;
bool a[N][N];
bool b[N][N];
bool bl[N][N];
bool ur[N][N];
bool used[N][N];
set<int>dt[N];
set<int>dc[N];
int urc[N], urt[N];
int blc[N], blt[N];
void kpcruBL(int i, int j){
bl[i][j]=true;
a[i][j]=true;
for(int jj=1;jj<=j;jj++){
a[i][jj]=true;
bl[i][jj]=true;
}
for(int ii=i;ii<n;ii++){
a[ii][j]=true;
bl[ii][j]=true;
}
}
void kpcruUR(int i, int j){
ur[i][j]=true;
a[i][j]=true;
for(int jj=j;jj<m;jj++){
a[i][jj]=true;
ur[i][jj]=true;
}
for(int ii=1;ii<=i;ii++){
a[ii][j]=true;
ur[ii][j]=true;
}
}
void gnaUR(int i, int j){
kpcruUR(i,j);
for(int ii=i-1;ii<=i+1;ii++){
for(int jj=j-1;jj<=j+1;jj++){
if(a[ii][jj]&&!(ii==i&&jj==j)&&!ur[ii][jj]){
gnaUR(ii,jj);
}
}
}
}
void gnaBL(int i, int j){
kpcruBL(i,j);
for(int ii=i-1;ii<=i+1;ii++){
for(int jj=j-1;jj<=j+1;jj++){
if(a[ii][jj]&&!(ii==i&&jj==j)&&!bl[ii][jj]){
gnaBL(ii,jj);
}
}
}
}
int query(int i, int j){
bool urka=false;
bool blka=false;
for(int ii=i-1;ii<=i+1;ii++){
for(int jj=j-1;jj<=j+1;jj++){
if(a[ii][jj]&&!(ii==i&&jj==j)){
if(ur[ii][jj])urka=true;
if(bl[ii][jj])blka=true;
}
}
}
if(urka&&blka)return 0;
if(urka){
gnaUR(i,j);
}
if(blka){
gnaBL(i,j);
}
return 1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0;i<=n+1;i++){
for(int j=0;j<=m+1;j++){
if(i==0||i==n+1||j==0||j==m+1){
a[i][j]=true;
if(i==0||j==m+1)ur[i][j]=true;
else bl[i][j]=true;
continue;
}
cin>>b[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(b[i][j])query(i,j);
}
}
// for(int i=1;i<=n;i++){
// urt[i]=m+10;
// blt[i]=-10;
// }
// for(int j=1;j<=m;j++){
// blc[j]=n+10;
// urc[j]=-10;
// }
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// if(ur[i][j]){
// urc[j]=max(urc[j],i);
// urt[i]=min(urt[i],j);
// }
// if(bl[i][j]){
// blc[j]=min(blc[j],i);
// blt[i]=max(blt[i],j);
// }
// }
// }
// urt[0]=0;
// urc[m+1]=n;
// for(int i=1;i<=n;i++){
// auto it=dt[i].lower_bound(urt[i-1]-1);
// urt[i]=m+10;
// if(it!=dt[i].end())urt[i]=*it;
// for(int j=m;j>=1;j--){
// auto itt=dc[j].upper_bound(urc[j+1]+1);
// urc[j]=-10;
// if(itt!=dc[j].begin())urc[j]=*(--itt);
// if(urt[i]<=j||urc[j]>=i){
// a[i][j]=true;
// ur[i][j]=true;
// dt[i].insert(j);
// dc[j].insert(i);
// }
// }
// }
// blt[n+1]=m;
// blc[0]=0;
// for(int i=n;i>=1;i--){
// auto it=dt[i].upper_bound(blt[i+1]+1);
// blt[i]=-10;
// if(it!=dt[i].begin())blt[i]=*(--it);
// // cout<<"i - "<<i<<": "<<blt[i]<<endl;
// for(int j=1;j<=m;j++){
// // cout<<"dc: ";
// // for(int x:dc[j]){
// // cout<<x<<" ";
// // }
// // cout<<endl;
// auto itt=dc[j].lower_bound(blc[j-1]-1);
// blc[j]=n+10;
// if(itt!=dc[j].end())blc[j]=*itt;
// // cout<<"j - "<<j<<": "<<blc[j]<<endl;
// if(blt[i]>=j||blc[j]<=i){
// a[i][j]=true;
// // cout<<i<<", "<<j<<": "<<blt[i]<<" "<<blc[j]<<endl;
// bl[i][j]=true;
// dt[i].insert(j);
// dc[j].insert(i);
// }
// }
// }
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<a[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<bl[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<ur[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
cin>>k;
for(int c=0;c<k;c++){
int i,j;
cin>>i>>j;
cout<<query(i,j)<<endl;
// assert(false);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
852 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
