//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;int m;int Q;
int gr[1010][1010];
int rch[1010][1010];
int rrch[1010][1010];
int okcnt[3010];
void precalc(){
queue<pair<int,int>>q;
q.push({1,1});
rch[1][1]=1;
while(q.size()){
int nwx=q.front().first;
int nwy=q.front().second;
q.pop();
int x=nwx;int y=nwy;
x++;
if(gr[x][y]==0&&rch[x][y]==0&&x<=n&&y<=m){
rch[x][y]=1;
q.push({x,y});
}
x--;y++;
if(gr[x][y]==0&&rch[x][y]==0&&x<=n&&y<=m){
rch[x][y]=1;
q.push({x,y});
}
}
q.push({n,m});
rch[n][m]=1;
while(q.size()){
int nwx=q.front().first;
int nwy=q.front().second;
q.pop();
int x=nwx;int y=nwy;
x--;
if(gr[x][y]==0&&rrch[x][y]==0){
rrch[x][y]=1;
q.push({x,y});
}
x++;y--;
if(gr[x][y]==0&&rrch[x][y]==0){
rrch[x][y]=1;
q.push({x,y});
}
}
}
void bkupd(int stx,int sty){
queue<pair<int,int>>q;
q.push({stx,sty});
while(q.size()){
int nwx=q.front().first;
int nwy=q.front().second;
q.pop();
int x=nwx-1;int y=nwy;
if(rrch[x][y]==1&&rrch[x][y+1]==0){
rrch[x][y]=0;
if(rch[x][y]==1){
okcnt[x+y]--;
}
q.push({x,y});
}
x=nwx;y=nwy-1;
if(rrch[x][y]==1&&rrch[x+1][y]==0){
rrch[x][y]=0;
if(rch[x][y]==1){
okcnt[x+y]--;
}
q.push({x,y});
}
}
}
void frupd(int stx,int sty){
queue<pair<int,int>>q;
q.push({stx,sty});
while(q.size()){
int nwx=q.front().first;
int nwy=q.front().second;
q.pop();
int x=nwx+1;int y=nwy;
if(rch[x][y]==1&&rch[x][y-1]==0){
rch[x][y]=0;
if(rrch[x][y]==1){
okcnt[x+y]--;
}
q.push({x,y});
}
x=nwx;y=nwy+1;
if(rch[x][y]==1&&rch[x-1][y]==0){
rch[x][y]=0;
if(rrch[x][y]==1){
okcnt[x+y]--;
}
q.push({x,y});
}
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>gr[i][j];
}
}
precalc();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(rch[i][j]&&rrch[i][j]){
okcnt[i+j]++;
}
}
}
cin>>Q;
while(Q--){
int x;int y;
cin>>x>>y;
if(rch[x][y]&&rrch[x][y]){
if(okcnt[x+y]==1){
cout<<0<<"\n";
continue;
}
}
if(rch[x][y]){
frupd(x,y);
}
if(rrch[x][y]){
bkupd(x,y);
}
if(rch[x][y]&&rrch[x][y]){okcnt[x+y]--;}
rch[x][y]=0;rrch[x][y]=0;
cout<<"1\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
7 ms |
9816 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
7 ms |
9816 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |