#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bitset>
#include <chrono>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int n, m;
cin >> n >> m;
vector <vector <int>> c(n, vector <int> (m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> c[i][j];
c[i][j] ^= 1;
}
}
vector <vector <int>> from_start(n, vector <int> (m)), from_finish(n, vector <int> (m));
from_start[0][0] = 1;
from_finish[n - 1][m - 1] = 1;
auto is_ok_start = [&] (int i, int j) {
int ok = 0;
if (i > 0) ok |= from_start[i - 1][j];
if (j > 0) ok |= from_start[i][j - 1];
return ok;
};
auto is_ok_finish = [&] (int i, int j) {
int ok = 0;
if (i + 1 < n) ok |= from_finish[i + 1][j];
if (j + 1 < m) ok |= from_finish[i][j + 1];
return ok;
};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i == 0 && j == 0) continue;
from_start[i][j] = c[i][j] & is_ok_start(i, j);
}
}
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
if (i == n - 1 && j == m - 1) continue;
from_finish[i][j] = c[i][j] & is_ok_finish(i, j);
}
}
/*for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cout << from_finish[i][j] << ' ';
}
cout << '\n';
}*/
auto ok = [&] (int i, int j) {
return from_start[i][j] & from_finish[i][j];
};
vector <int> cnt(n + m - 1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (ok(i, j)) {
++cnt[i + j];
}
}
}
function <void(int, int)> kill_start = [&] (int i, int j) {
if (from_start[i][j] == 0) return;
if (ok(i, j)) --cnt[i + j];
from_start[i][j] = 0;
if (i + 1 < n && from_start[i + 1][j] == 1 && !is_ok_start(i + 1, j)) kill_start(i + 1, j);
if (j + 1 < m && from_start[i][j + 1] == 1 && !is_ok_start(i, j + 1)) kill_start(i, j + 1);
};
function <void(int, int)> kill_finish = [&] (int i, int j) {
if (from_finish[i][j] == 0) return;
if (ok(i, j)) --cnt[i + j];
from_finish[i][j] = 0;
if (i > 0 && from_finish[i - 1][j] == 1 && !is_ok_finish(i - 1, j)) kill_finish(i - 1, j);
if (j > 0 && from_start[i][j - 1] == 1 && !is_ok_finish(i, j - 1)) kill_finish(i, j - 1);
};
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
--x, --y;
if (ok(x, y) && cnt[x + y] == 1) {
cout << "0\n";
continue;
}
cout << "1\n";
kill_start(x, y);
kill_finish(x, y);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
4 ms |
512 KB |
Output is correct |
5 |
Correct |
4 ms |
512 KB |
Output is correct |
6 |
Correct |
4 ms |
640 KB |
Output is correct |
7 |
Correct |
4 ms |
640 KB |
Output is correct |
8 |
Correct |
3 ms |
640 KB |
Output is correct |
9 |
Correct |
5 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
512 KB |
Output is correct |
3 |
Correct |
2 ms |
512 KB |
Output is correct |
4 |
Correct |
4 ms |
512 KB |
Output is correct |
5 |
Correct |
4 ms |
512 KB |
Output is correct |
6 |
Correct |
4 ms |
640 KB |
Output is correct |
7 |
Correct |
4 ms |
640 KB |
Output is correct |
8 |
Correct |
3 ms |
640 KB |
Output is correct |
9 |
Correct |
5 ms |
768 KB |
Output is correct |
10 |
Correct |
12 ms |
1280 KB |
Output is correct |
11 |
Correct |
3 ms |
512 KB |
Output is correct |
12 |
Correct |
241 ms |
16248 KB |
Output is correct |
13 |
Correct |
80 ms |
12536 KB |
Output is correct |
14 |
Correct |
423 ms |
20524 KB |
Output is correct |
15 |
Correct |
448 ms |
20320 KB |
Output is correct |
16 |
Correct |
464 ms |
21976 KB |
Output is correct |
17 |
Correct |
447 ms |
23272 KB |
Output is correct |
18 |
Correct |
434 ms |
22648 KB |
Output is correct |
19 |
Correct |
458 ms |
24068 KB |
Output is correct |
20 |
Correct |
329 ms |
23984 KB |
Output is correct |
21 |
Correct |
448 ms |
23976 KB |
Output is correct |