#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=1000, dx[8]={-1, -1, -1, 0, 0, 1, 1, 1}, dy[8]={-1, 0, 1, -1, 1, -1, 0, 1};
int n, m, q, c[mxN][mxN], p[mxN*mxN+2];
vector<int> oc[mxN];
int find(int i) {
return i^p[i]?p[i]=find(p[i]):i;
}
int find(int i, int j) {
return find(i*m+j);
}
int mrg(int u, int v) {
if (u<v)
swap(u, v);
p[v]=u;
return u;
}
int prv(int i, int j) {
if (i==0||j<=1||oc[i-1].empty()||oc[i-1][0]>j-2)
return -1;
int pos=upper_bound(oc[i-1].begin(), oc[i-1].end(), j-2)-oc[i-1].begin();
assert(pos>0);
return oc[i-1][pos-1];
}
int nxt(int i, int j) {
if (i==n-1||j+2>=m||oc[i+1].empty()||oc[i+1].back()<j+2)
return -1;
auto it=lower_bound(oc[i+1].begin(), oc[i+1].end(), j+2);
assert(it!=oc[i+1].end());
return *it;
}
bool bad(int i, int j) {
bool leftdown=i==n-1||j==0, upright=i==0||j==m-1;
for (int k=0; k<8; ++k) {
int ni=i+dx[k], nj=j+dy[k];
if (0<=ni&&ni<n&&0<=nj&&nj<m&&c[ni][nj]) {
int u=find(ni, nj);
if (u==n*m)
leftdown=1;
if (u==n*m+1)
upright=1;
}
}
int x=prv(i, j), y=nxt(i, j);
if (y!=-1) leftdown|=find(i+1, y)==n*m;
if (x!=-1) upright|=find(i-1, x)==n*m+1;
//cout << x << " " << y << " " << leftdown << " " << upright << endl;
return leftdown&&upright;
}
void add(int i, int j) {
int u=i*m+j;
if (i==n-1||j==0)
u=mrg(u, n*m);
if (i==0||j==m-1)
u=mrg(u, n*m+1);
for (int k=0; k<8; ++k) {
int ni=i+dx[k], nj=j+dy[k];
if (0<=ni&&ni<n&&0<=nj&&nj<m&&c[ni][nj]) {
int v=find(ni, nj);
if (u!=v)
u=mrg(u, v);
}
}
int x=prv(i, j), y=nxt(i, j);
if (y!=-1) {
int v=find(i+1, y);
if (u!=v)
u=mrg(u, v);
}
if (x!=-1) {
int v=find(i-1, x);
if (u!=v)
u=mrg(u, v);
}
c[i][j]=1;
oc[i].push_back(j);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
iota(p, p+n*m+2, 0);
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j) {
cin >> c[i][j];
if (c[i][j])
add(i, j);
}
cin >> q;
while(q--) {
int i, j;
cin >> i >> j, --i, --j;
assert(!c[i][j]);
bool ans=!bad(i, j);
cout << ans << "\n";
if (ans)
add(i, j);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
