#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;
const ll inf=1001001001001;
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,inf);
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]--;
assert(cnt[nx.fi+nx.se]>0);
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]--;
assert(cnt[nx.fi+nx.se]>0);
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;que.emplace(x,y);sols();
t[x][y]=false;que.emplace(x,y);solt();
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
468 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
5 ms |
468 KB |
Output is correct |
7 |
Correct |
4 ms |
468 KB |
Output is correct |
8 |
Correct |
4 ms |
468 KB |
Output is correct |
9 |
Correct |
4 ms |
468 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
468 KB |
Output is correct |
4 |
Correct |
4 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
5 ms |
468 KB |
Output is correct |
7 |
Correct |
4 ms |
468 KB |
Output is correct |
8 |
Correct |
4 ms |
468 KB |
Output is correct |
9 |
Correct |
4 ms |
468 KB |
Output is correct |
10 |
Correct |
13 ms |
1160 KB |
Output is correct |
11 |
Correct |
3 ms |
460 KB |
Output is correct |
12 |
Correct |
184 ms |
13672 KB |
Output is correct |
13 |
Correct |
73 ms |
11132 KB |
Output is correct |
14 |
Correct |
313 ms |
17940 KB |
Output is correct |
15 |
Correct |
297 ms |
16920 KB |
Output is correct |
16 |
Correct |
318 ms |
18372 KB |
Output is correct |
17 |
Correct |
376 ms |
19484 KB |
Output is correct |
18 |
Correct |
366 ms |
19008 KB |
Output is correct |
19 |
Correct |
382 ms |
20064 KB |
Output is correct |
20 |
Correct |
352 ms |
20024 KB |
Output is correct |
21 |
Correct |
386 ms |
20008 KB |
Output is correct |