#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple
const int N = 1010;
int n, m, q;
bool lu[N][N];
bool rd[N][N];
bool dp[N][N];
int fen[N][N];
int pref(int x, int y) {
int s = 0;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
for (int j = y; j >= 0; j = (j & (j + 1)) - 1) {
s += fen[i][j];
}
}
return s;
}
bool rec(int a, int b, int c, int d) {
--a;
--c;
return pref(b, d) - pref(a, d) - pref(b, c) + pref(a, c) > 0;
}
void upd(int x, int y, int d) {
for (int i = x; i < N; i |= i + 1) {
for (int j = y; j < N; j |= j + 1) {
fen[i][j] += d;
}
}
}
bool can_off(int i, int j) {
if (!dp[i][j]) {
return true;
}
return rec(1, i - 1, j + 1, m) || rec(i + 1, n, 1, j - 1);
}
void lu_dfs(int i, int j) {
if (i < 1 || j < 1) {
return;
}
if (dp[i][j] && !dp[i + 1][j] && !dp[i][j + 1]) {
dp[i][j] = false;
upd(i, j, -1);
lu_dfs(i - 1, j);
lu_dfs(i, j - 1);
}
}
void rd_dfs(int i, int j) {
if (i > n || j > m) {
return;
}
if (dp[i][j] && !dp[i - 1][j] && !dp[i][j - 1]) {
dp[i][j] = false;
upd(i, j, -1);
rd_dfs(i + 1, j);
rd_dfs(i, j + 1);
}
}
void print() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cout << dp[i][j] << " ";
}
cout << "\n";
}
}
signed main() {
#ifdef LC
assert(freopen("input.txt", "r", stdin));
#endif
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> dp[i][j];
dp[i][j] ^= 1;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
lu[i][j] = dp[i][j] && (lu[i - 1][j] || lu[i][j - 1]);
lu[1][1] = true;
}
}
for (int i = n; i >= 1; --i) {
for (int j = m; j >= 1; --j) {
rd[i][j] = dp[i][j] && (rd[i + 1][j] || rd[i][j + 1]);
rd[n][m] = true;
dp[i][j] = lu[i][j] & rd[i][j];
upd(i, j, dp[i][j]);
}
}
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
if (can_off(x, y)) {
dp[x][y] = false;
upd(x, y, -1);
lu_dfs(x - 1, y);
lu_dfs(x, y - 1);
rd_dfs(x + 1, y);
rd_dfs(x, y + 1);
cout << "1\n";
} else {
cout << "0\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
896 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1152 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
896 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1152 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
