#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>> bad;
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)) {
bad.emplace_back(i, j);
} else if (degIn[i][j] == 0 && (i != 0 || j != 0)) {
bad.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) {
bad.emplace_back(i + 1, j);
}
}
if (j + 1 < m && a[i][j + 1] == '0') {
if (--degIn[i][j + 1] == 0) {
bad.emplace_back(i, j + 1);
}
}
if (i - 1 >= 0 && a[i - 1][j] == '0') {
if (--degOut[i - 1][j] == 0) {
bad.emplace_back(i - 1, j);
}
}
if (j - 1 >= 0 && a[i][j - 1] == '0') {
if (--degOut[i][j - 1] == 0) {
bad.emplace_back(i, j - 1);
}
}
};
auto purify = [&]() -> void {
while (!bad.empty()) {
auto [i, j] = bad.back();
bad.pop_back();
// cerr << i << ' ' << j << '\n';
erase(i, j);
}
};
auto print = [&]() -> void {
for (int r = 0; r < n; ++r) {
for (int c = 0; c < m; ++c) {
cerr << a[r][c] << ' ';
}
cerr << '\n';
}
cerr << "---\n";
};
purify();
// print();
// 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';
// print();
}
}
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;
}
Compilation message
furniture.cpp: In function 'void solve()':
furniture.cpp:111:10: warning: variable 'print' set but not used [-Wunused-but-set-variable]
111 | auto print = [&]() -> void {
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
604 KB |
Output is correct |
| 4 |
Correct |
2 ms |
604 KB |
Output is correct |
| 5 |
Correct |
3 ms |
604 KB |
Output is correct |
| 6 |
Correct |
3 ms |
604 KB |
Output is correct |
| 7 |
Correct |
2 ms |
604 KB |
Output is correct |
| 8 |
Correct |
2 ms |
604 KB |
Output is correct |
| 9 |
Correct |
3 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
604 KB |
Output is correct |
| 4 |
Correct |
2 ms |
604 KB |
Output is correct |
| 5 |
Correct |
3 ms |
604 KB |
Output is correct |
| 6 |
Correct |
3 ms |
604 KB |
Output is correct |
| 7 |
Correct |
2 ms |
604 KB |
Output is correct |
| 8 |
Correct |
2 ms |
604 KB |
Output is correct |
| 9 |
Correct |
3 ms |
604 KB |
Output is correct |
| 10 |
Correct |
8 ms |
1372 KB |
Output is correct |
| 11 |
Correct |
2 ms |
660 KB |
Output is correct |
| 12 |
Correct |
161 ms |
17236 KB |
Output is correct |
| 13 |
Correct |
64 ms |
13812 KB |
Output is correct |
| 14 |
Correct |
226 ms |
21584 KB |
Output is correct |
| 15 |
Correct |
225 ms |
21076 KB |
Output is correct |
| 16 |
Correct |
201 ms |
22752 KB |
Output is correct |
| 17 |
Correct |
216 ms |
23892 KB |
Output is correct |
| 18 |
Correct |
249 ms |
23380 KB |
Output is correct |
| 19 |
Correct |
244 ms |
24688 KB |
Output is correct |
| 20 |
Correct |
212 ms |
24860 KB |
Output is correct |
| 21 |
Correct |
229 ms |
24660 KB |
Output is correct |
