#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 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){
for(int jj=blt[i]+1;jj<=j;jj++){
a[i][jj]=true;
bl[i][jj]=true;
}
for(int ii=i;ii<blc[j];ii++){
a[ii][j]=true;
bl[ii][j]=true;
}
}
void kpcruUR(int i, int j){
for(int jj=j;jj<blt[i];jj++){
a[i][jj]=true;
ur[i][jj]=true;
}
for(int ii=blc[j]+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>>a[i][j];
if(a[i][j]){
dt[i].insert(j);
dc[j].insert(i);
}
}
}
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 |
Runtime error |
251 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Runtime error |
251 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
