#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<vector<bool>> bad(N+2, vector<bool>(M+2, 0));
int dcnt[N+M+1] = {};
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
bool b;
cin >> b;
bad[i][j] = b;
dcnt[i+j] += bad[i][j];
}
}
for (int i = 0; i < N+2; i++) {
bad[i][0] = bad[i][M+1] = 1;
}
for (int i = 0; i < M+2; i++) {
bad[0][i] = bad[N+1][i] = 1;
}
auto yeet = [&](int X, int Y) {
vector<ari2> qu;
qu.push_back({X, Y});
dcnt[X+Y] += !bad[X][Y];
bad[X][Y] = 1;
while (qu.size()) {
auto [i, j] = qu.back();
qu.pop_back();
if (bad[i-1][j+1]) {
if (!bad[i-1][j]) {
qu.push_back({i-1, j});
dcnt[i-1+j]++;
}
if (!bad[i][j+1]) {
qu.push_back({i, j+1});
dcnt[i+j+1]++;
}
bad[i-1][j] = bad[i][j+1] = 1;
}
if (bad[i+1][j-1]) {
if (!bad[i][j-1]) {
qu.push_back({i, j-1});
dcnt[i+j-1]++;
}
if (!bad[i+1][j]) {
qu.push_back({i+1, j});
dcnt[i+1+j]++;
}
bad[i][j-1] = bad[i+1][j] = 1;
}
}
};
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (!bad[i][j]) continue;
yeet(i, j);
}
}
int Q;
for (cin >> Q; Q--; ) {
int i, j;
cin >> i >> j;
if (bad[i][j] || dcnt[i+j] < min(N, i+j) - max(1, i+j-M)) {
yeet(i, j);
cout << "1\n";
} else {
cout << "0\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
