#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];
set<int> row[mxN], col[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);
}
void mrg(int u, int v) {
if (u<v)
swap(u, v);
p[v]=u;
}
vector<ar<int, 2>> get_adj(int i, int j) {
vector<ar<int, 2>> v;
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])
v.push_back({ni, nj});
}
return v;
}
bool bad(int i, int j) {
bool leftdown=i==n-1||j==0, upright=i==0||j==m-1;
for (auto [x, y] : get_adj(i, j)) {
//cout << i << " " << j << " " << x << " " << y << endl;
leftdown|=find(x, y)==n*m;
upright|=find(x, y)==n*m+1;
}
return leftdown&&upright;
}
void add(int i, int j) {
if (i==n-1||j==0)
mrg(find(i, j), n*m);
if (i==0||j==m-1)
mrg(find(i, j), n*m+1);
for (auto [x, y] : get_adj(i, j))
mrg(find(i, j), find(x, y));
c[i][j]=1;
row[i].insert(j);
col[j].insert(i);
}
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]);
if (bad(i, j)) {
cout << "0\n";
continue;
}
c[i][j]=1;
row[i].insert(j);
col[j].insert(i);
int last=-1;
bool ok=1;
for (int i=0; i<n; ++i) {
if (row[i].empty()||*row[i].rbegin()<last-1) {
ok=0;
break;
}
last=*row[i].lower_bound(last-1);
while(last&&c[i][last-1])
--last;
if (!last)
break;
}
if (ok) {
c[i][j]=0;
row[i].erase(j);
col[j].erase(i);
cout << "0\n";
continue;
}
last=-1, ok=1;
for (int i=0; i<m; ++i) {
if (col[i].empty()||*col[i].rbegin()<last-1) {
ok=0;
break;
}
last=*col[i].lower_bound(last-1);
while(last&&c[last-1][i])
--last;
if (!last)
break;
}
if (ok) {
c[i][j]=0;
row[i].erase(j);
col[j].erase(i);
cout << "0\n";
continue;
}
cout << "1\n";
add(i, j);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
1100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
1100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
