# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=1005;
long long n,m,fix[3][N][N],x,y,a,b,aa[N][N],mp[3*N],r[N][N],qq,ans[1000*N];
queue< pair <int ,int > > q;
int check1(int x, int y) {
if((y==1 || r[x][y-1]==1) && (x==1 || r[x-1][y]==1))
return 1;
else return 0;
}
int check2(int x, int y) {
if((y==m ||r[x][y+1]==1) && (x==n || r[x+1][y]==1))
return 1;
else return 0;
}
int check(int x, int y) {
if (x>n || y>m || x<1 || y<1) return 0;
else return 1;
}
void go(int a, int b, int ty) {
if (fix[ty+1][a][b]==1) return;
fix[ty+1][a][b]=1;
if (check(a+ty,b) && aa[a+ty][b]==0) go(a+ty,b,ty);
if (check(a,ty+b) && aa[a][ty+b]==0) go(a,ty+b,ty);
}
void update1(int a,int b){
x=a;
y=b;
if(check(x+1,y) && r[x+1][y]==0 && r[x+1][y-1]==1) q.push({x+1,y});
if(check(x,y+1) && r[x][y+1]==0 && r[x-1][y+1]==1) q.push({x,y+1});
while(q.size()){
x=q.front().f;
y=q.front().s;
q.pop();
if(r[x][y-1]==0 || r[x-1][y]==0) continue;
r[x][y]=1; mp[x+y]--;
if(check(x+1,y) && r[x+1][y]==0 && r[x+1][y-1]==1) q.push({x+1,y});
if(check(x,y+1) && r[x][y+1]==0 && r[x-1][y+1]==1) q.push({x,y+1});
}
}
void update2(int a,int b){
x=a;
y=b;
if(check(x-1,y) && r[x-1][y]==0 && 1==r[x-1][y+1]) q.push({x-1,y});
if(check(x,y-1) && r[x][y-1]==0 && 1==r[x+1][y-1]) q.push({x,y-1});
while(q.size()){
x=q.front().f;
y=q.front().s;
q.pop();
if(r[x][y+1]==0 || r[x+1][y]==0) continue;
r[x][y]=1; mp[x+y]--;
if(check(x-1,y) && r[x-1][y]==0 && 1==r[x-1][y+1]) q.push({x-1,y});
if(check(x,y-1) && r[x][y-1]==0 && 1==r[x+1][y-1]) q.push({x,y-1});
}
}
int main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
cin>>aa[i][j];
}
}
go(1,1,1);
go(n,m,-1);
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
if (fix[0][i][j] && fix[2][i][j]) {
r[i][j]=0;
mp[i+j]++;
} else r[i][j]=1;
}
}
cin>>qq;
for (int i=1; i<=qq; i++) {
cin>>x>>y;
if (r[x][y]==1) {
ans[i]=1;
continue;
}
if (mp[x+y]==1) {
ans[i]=0;
continue;
}
ans[i]=1;
mp[x+y]--;
r[x][y]=1;
update1(x,y);
update2(x,y);
}
for (int i=1; i<=qq; i++)
cout<<ans[i]<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1612 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
1996 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1612 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
1996 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
