#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
int n, m;
vector<vector<int>> fen;
Fenwick() {}
Fenwick(int _n, int _m) {
n = _n, m = _m;
fen.resize(n + 1, vector<int>(m + 1));
}
void add(int i, int j, int x) {
for (int row = i; row <= n; row += (row & -row)) {
for (int col = j; col <= m; col += (col & -col)) {
// cerr << row << ' ' << col << '\n';
fen[row][col] += x;
}
}
}
int getPref(int i, int j) {
int res = 0;
for (int row = i; row > 0; row -= (row & -row)) {
for (int col = j; col > 0; col -= (col & -col)) {
res += fen[row][col];
}
}
return res;
}
int getSum(int li, int lj, int ri, int rj) {
return getPref(ri, rj) - getPref(li - 1, rj) - getPref(ri, lj - 1) + getPref(li - 1, lj - 1);
}
~Fenwick() {}
};
void solve() {
int n, m;
cin >> n >> m;
vector<vector<char>> a(n, vector<char>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
vector<vector<int>> degIn(n, vector<int>(m, -1)), degOut(n, vector<int>(m, -1));
vector<pair<int, int>> badOut, badIn;
Fenwick fen(n, m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] == '0') {
degOut[i][j] = 0;
if (i + 1 < n && a[i + 1][j] == '0') {
++degOut[i][j];
}
if (j + 1 < m && a[i][j + 1] == '0') {
++degOut[i][j];
}
degIn[i][j] = 0;
if (i - 1 >= 0 && a[i - 1][j] == '0') {
++degIn[i][j];
}
if (j - 1 >= 0 && a[i][j - 1] == '0') {
++degIn[i][j];
}
if (degOut[i][j] == 0 && (i != n - 1 || j != m - 1)) {
badOut.emplace_back(i, j);
}
if (degIn[i][j] == 0 && (i != 0 || j != 0)) {
badIn.emplace_back(i, j);
}
fen.add(i + 1, j + 1, 1);
}
}
}
// cerr << "!\n";
auto erase = [&](int i, int j) -> void {
assert(i != 0 || j != 0 || i != n - 1 || j != m - 1);
if (a[i][j] == '1') {
return;
}
a[i][j] = '1';
degIn[i][j] = degOut[i][j] = 0;
fen.add(i + 1, j + 1, -1);
if (i + 1 < n && a[i + 1][j] == '0') {
if (--degIn[i + 1][j] == 0) {
badIn.emplace_back(i, j);
}
}
if (j + 1 < m && a[i][j + 1] == '0') {
if (--degIn[i][j + 1] == 0) {
badIn.emplace_back(i, j);
}
}
if (i - 1 >= 0 && a[i - 1][j] == '0') {
if (--degOut[i - 1][j] == 0) {
badOut.emplace_back(i - 1, j);
}
}
if (j - 1 >= 0 && a[i][j - 1] == '0') {
if (--degOut[i][j - 1] == 0) {
badOut.emplace_back(i, j - 1);
}
}
};
auto purify = [&]() -> void {
while (!badOut.empty() || !badIn.empty()) {
if (!badOut.empty()) {
auto [i, j] = badOut.back();
badOut.pop_back();
// cerr << i << ' ' << j << '\n';
erase(i, j);
} else {
auto [i, j] = badIn.back();
badIn.pop_back();
// cerr << i << ' ' << j << '\n';
erase(i, j);
}
}
};
purify();
// cerr << "!!\n";
int q;
cin >> q;
while (q--) {
int i, j;
cin >> i >> j;
if (a[i - 1][j - 1] == '0' && fen.getSum(i + 1, 1, n, j - 1) + fen.getSum(1, j + 1, i - 1, m) > 0) {
// cerr << "!\n";
erase(i - 1, j - 1);
purify();
}
cout << a[i - 1][j - 1] << '\n';
/*for (int r = 0; r < n; ++r) {
for (int c = 0; c < m; ++c) {
cerr << a[r][c] << ' ';
}
cerr << '\n';
}*/
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
540 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
