#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
const ll mod=1000000007;
ll modpow(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
int main(){
cin.tie(0);ios::sync_with_stdio(false);
ll n,m;cin>>n>>m;
vvi v(n,vi(m));
rep(i,n)rep(j,m)cin>>v[i][j];
vvb s(n,vb(m,true)),t(n,vb(m,true));
queue<P> que;
vi dx={1,0,0,-1},dy={0,1,-1,0};
vi cnt(n+m-1);
auto sols=[&](){
while(!que.empty()){
auto x=que.front();que.pop();
rep(k,2){
P nx(x.fi+dx[k],x.se+dy[k]);
if(nx.fi<n&&nx.se<m&&s[nx.fi][nx.se]){
P nnx(nx.fi-dx[1-k],nx.se-dy[1-k]);
if(nnx.fi>=0&&nnx.se>=0&&s[nnx.fi][nnx.se])continue;
if(t[nx.fi][nx.se])cnt[nx.fi+nx.se]--;
s[nx.fi][nx.se]=false;que.emplace(nx);
}
}
}
};
auto solt=[&](){
while(!que.empty()){
auto x=que.front();que.pop();
REP(k,2,4){
P nx(x.fi+dx[k],x.se+dy[k]);
if(nx.fi>=0&&nx.se>=0&&t[nx.fi][nx.se]){
P nnx(nx.fi-dx[5-k],nx.se-dy[5-k]);
if(nnx.fi<n&&nnx.se<m&&t[nnx.fi][nnx.se])continue;
if(s[nx.fi][nx.se])cnt[nx.fi+nx.se]--;
t[nx.fi][nx.se]=false;que.emplace(nx);
}
}
}
};
rep(i,n)rep(j,m)if(v[i][j]){
s[i][j]=false;que.emplace(i,j);
}sols();
rep(i,n)rep(j,m)if(v[i][j]){
t[i][j]=false;que.emplace(i,j);
}solt();
rep(i,n+m-1)cnt[i]=0;
rep(i,n)rep(j,m)if(s[i][j]&&t[i][j])cnt[i+j]++;
// outvv(s);
// outvv(t);
// outv(cnt);
ll q;cin>>q;
rep(qq,q){
ll x,y;cin>>x>>y;x--;y--;
if(s[x][y]&&t[x][y]&&cnt[x+y]==1)out(0);
else{
out(1);
if(s[x][y]&&t[x][y])cnt[x+y]--;
s[x][y]=false;sols();
t[x][y]=false;solt();
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
